Home Bookmarks Papers Blog

High-Dimensional Shape Fitting in Linear Time

Sariel Har-Peled and Kasturi R. Varadarajan

Let P be a set of n points in Rd. The radius of a k-dimensional flat F with respect to P, which we denote by rad(F,P), is defined to be maxp in P D(F,p), where D(F,p) denotes the Euclidean distance between p and its projection onto F. The k-flat radius of P, which we denote by krad(P), is the minimum, over all k-dimensional flats F, of rad(F,P). We consider the problem of computing krad(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 NP-hard even for k = 1. We present an algorithm that, given P and a parameter 0 < µ <= 1, returns a k-flat F such that rad(F,P) <=(1 + µ) krad(P). The algorithm runs in O(nd Cµ,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 O(d nk/µ^5).

Postscript, PDF.

@string{DCG    = "Discrete Comput. Geom."}

  title        = {High-Dimensional Shape Fitting in Linear Time},
  author       = {S. {Har-Peled} and K. R. Varadarajan},
  year         = {2004},
  journal      = DCG,
  volume       = {32},
  number       = {2},
  pages        = {269--288},
  url          = {http://sarielhp.org/research/papers/02/pcluster/},

Last modified: Mon Aug 2 19:29:08 CDT 2004