Journal article
High-Dimensional Shape Fitting in Linear Time
Discrete & computational geometry, Vol.32(2), pp.269-288
07/2004
DOI: 10.1007/s00454-004-1118-2
Abstract
Let P be a set of n points in ℝd. The radius of a k-dimensional flat F with respect to P, which we denote 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 R kopt(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 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.
Details
- Title: Subtitle
- High-Dimensional Shape Fitting in Linear Time
- Creators
- Sariel Har-Peled - University of Illinois Urbana-ChampaignKasturi R. Varadarajan - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Discrete & computational geometry, Vol.32(2), pp.269-288
- DOI
- 10.1007/s00454-004-1118-2
- ISSN
- 0179-5376
- eISSN
- 1432-0444
- Language
- English
- Date published
- 07/2004
- Academic Unit
- Computer Science
- Record Identifier
- 9984259429002771
Metrics
13 Record Views