High-dimensional shape fitting in linear time

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/ec), where c is an appropriate constant.

REFERENCES

• 1: M. Badoiu and K. L. Clarkson. Optimal core-sets for balls. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, 801--802, 2003.
• 2: H. L. Bodlaender, P. Gritzmann, V. Klee, and J. van Leeuwen. The computational complexity of norm-maximization. Combinatorica, 10:203--225, 1990.
• 3: Gill Barequet , Sariel Har-Peled, Efficiently approximating the minimum-volume bounding box of a point set in three dimensions, Journal of Algorithms, v.38 n.1, p.91-109, Jan. 2001 [doi>10.1006/jagm.2000.1127 ]
• 4: Mihai Bādoiu , Sariel Har-Peled , Piotr Indyk, Approximate clustering via core-sets, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509947]
• 5: A. Brieden. On geometric optimization problems likely not contained in apx. to appear, 2002.
• 6: Herbert Edelsbrunner, Algorithms in combinatorial geometry, Springer-Verlag New York, Inc., New York, NY, 1987
• 7: U. Faigle , W. Kern , M. Streng, Note on the computational complexity of j-radii of polytopes in Rⁿ , Mathematical Programming: Series A and B, v.73 n.1, p.1-5, April 30, 1996 [doi>10.1007/BF02592095]
• 8: Peter Gritzmann , Victor Klee, Computational complexity of inner and outer j-radii of polytopes in finite-dimensional normed spaces, Mathematical Programming: Series A and B, v.59 n.2, p.163-213, April 14, 1993
• 9: Peter Gritzmann , Victor Klee, On the complexity of some basic problems in computational convexity: I.: containment problems, Discrete Mathematics, v.136 n.1-3, p.129-174, Dec. 31, 1994 [doi>10.1016/0012-365X(94)00111-U ]
• 10: M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, Berlin Heidelberg, 2nd edition, 1988. 2nd edition 1994.
• 11: S. Har-Peled, Approximate Shape Fitting via Linearization, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.66, October 14-17, 2001
• 12: Sariel Har-Peled , Kasturi Varadarajan, Projective clustering in high dimensions using core-sets, Proceedings of the eighteenth annual symposium on Computational geometry, p.312-318, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513440]
• 13: P. Kumar, J. S. B. Mitchell, and E. A. Yildirim. Fast smallest enclosing hypersphere computation. In Proc. 5th Workshop Algorithm Eng. Exper., 2003.
• 14: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 15: N. Megiddo, On the complexity of some geometric problems in unbounded dimension, Journal of Symbolic Computation, v.10 n.3-4, p.327-334, Sept./Oct. 1990 [doi>10.1016/S0747-7171(08)80067-3]
• 16: Y. Nesterov. Global quadratic optimization via conic relaxation. Technical report, Catholic University of Louvaine, Belgium, 1998.
• 17: A. Nemirovski, C. Roos, and T. Terlaky. On maximization of quadratic forms over intersection of ellipsoids with common center. Mathematical Programming, 86(3):463--473, 1999.
• 18: Kasturi R. Varadarajan , S. Venkatesh , Jiawei Zhang, On Approximating the Radii of Point Sets in High Dimensions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.561-569, November 16-19, 2002

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Theory

Keywords:
computational convexity, projective clustering