Logo image
Back
High-dimensional shape fitting in linear time
Conference proceeding   Peer reviewed

High-dimensional shape fitting in linear time

Sariel Har-Peled and Kasturi Varadarajan
Proceedings of the nineteenth annual symposium on computational geometry, pp.39-47
SCG '03
06/08/2003
DOI: 10.1145/777792.777799

View Online

Abstract

Let P be a set of n points in R d . The radius of a k -dimensional flat F with respect to P , denoted by RD(F,P) , is defined to be max p ? 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 R k opt (P) , is the minimum, over all k -dimensional flats F , of RD(F,P) . We consider the problem of computing R k opt (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) R k opt (P) . The algorithm runs in O(nd C e,k ) time, where C e,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 n O(k/e c ) , where c is an appropriate constant.
 computational convexity projective clustering

Details

Metrics

22 Record Views
Logo image