High-dimensional shape fitting in linear time
Sariel Har-Peled, Kasturi Varadarajan · 2003
Let P be a set of n points in Rd. 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 NP-hard even for k = 1. We present an algorithm that, given P and a parameter 0 < e = 1, returns a k-flat F such that RD(F,P) = (1 + e) Rkopt(P). The algorithm runs in O(nd Ce,k) time, where Ce,k is a constant that depends only on e 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 d nO(k/ec), where c is an appropriate constant.