High-dimensional shape fitting in linear time

Sariel Har-Peled, Kasturi Varadarajan

Research output: Contribution to conferencePaperpeer-review


Let P be a set of n points in ℝd. The radius of a k-dimensional flat F with respect to P, denoted by RD(F, P), is defined to be maxp∈P dist(F, p), where dist(F, p) denotes the Euclidean distance between p and its projection onto F. The k-flat radius of P, which we denote by Rkopt(P), is the minimum, over all k-dimensional flats F, of RD(F, P). We consider the problem of computing Rkopt(P) for a given set of points P. We are interested in the high-dimensional case where d is a part of the input and not a constant. This problem is ℕℙ-hard even for k = 1. We present an algorithm that, given P and a parameter 0 < ε ≤ 1, returns a k-flat F such that RD(F, P) ≤ (1 + ε)Rkopt(P). The algorithm runs in O(ndCε,k) time, where Cε,k is a constant that depends only on ε and k. Thus the algorithm runs in time linear in the size of the point set and is a substantial improvement over previous known algorithms, whose running time is of the order of dnO(k/εc) where c is an appropriate constant.

Original languageEnglish (US)
Number of pages9
StatePublished - 2003
EventNineteenth Annual Symposium on Computational Geometry - san Diego, CA, United States
Duration: Jun 8 2003Jun 10 2003


OtherNineteenth Annual Symposium on Computational Geometry
Country/TerritoryUnited States
Citysan Diego, CA


  • Computational convexity
  • Projective clustering

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'High-dimensional shape fitting in linear time'. Together they form a unique fingerprint.

Cite this