Journal article
Approximating the radii of point sets
SIAM journal on computing, Vol.36(6), pp.1764-1776
01/01/2007
DOI: 10.1137/050627472
Abstract
We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers n, d, and k, where k <= d, and a set P of n points in R-d. The goal is to compute the outer k-radius of P, denoted by R-k(P), which is the minimum over all (d - k)-dimensional flats F of max(p epsilon P) d(p, F), where d(p, F) is the Euclidean distance between the point p and flat F. Computing the radii of point sets is a fundamental problem in computational convexity with many significant applications. The problem admits a polynomial time algorithm when the dimension d is constant [U. Faigle, W. Kern, and M. Streng, Math. Program., 73 (1996), pp. 1-5]. Here we are interested in the general case in which the dimension d is not fixed and can be as large as n, where the problem becomes NP-hard even for k = 1. It is known that R-k(P) can be approximated in polynomial time by a factor of (1 + epsilon) for any epsilon > 0 when d - k is a fixed constant [M. Badoiu, S. Har-Peled, and P. Indyk, in Proceedings of the ACM Symposium on the Theory of Computing, 2002; S. Har-Peled and K. Varadarajan, in Proceedings of the ACM Symposium on Computing Geometry, 2002]. A polynomial time algorithm that guarantees a factor of O(root log n) approximation for R-1(P), the width of the point set P, is implied by the results of Nemirovski, Roos, and Terlaky [Math. Program., 86 (1999), pp. 463-473] and Nesterov [Handbook of Semidefinite Programming Theory, Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000]. In this paper, we show that R-k(P) can be approximated by a ratio of O(root log n) for any 1 <= k <= d, thus matching the previously best known ratio for approximating the special case R-1(P), the width of point set P. Our algorithm is based on semidefinite programming relaxation with a new mixed deterministic and randomized rounding procedure. We also prove an inapproximability result that gives evidence that our approximation algorithm is doing well for a large range of k. We show that there exists a constant delta > 0 such that the following holds for any 0 < epsilon < 1: there is no polynomial time algorithm that approximates R-k(P) within (log n)(delta) for all k such that k <= d - d(epsilon) unless NP subset of DTIME [2((logm)) (O(1))]. Our inapproximability result for R-k(P) extends a previously known hardness result of Brieden [ Discrete Comput. Geom., 28 (2002), pp. 201-209] and is proved by modifying Brieden's construction using basic ideas from probabilistically checkable proofs ( PCP) theory.
Details
- Title: Subtitle
- Approximating the radii of point sets
- Creators
- Kasturi Varadarajan - University of IowaS. Venkatesh - University of VictoriaYinyu Ye - Stanford UniversityJiawei Zhang - New York University
- Resource Type
- Journal article
- Publication Details
- SIAM journal on computing, Vol.36(6), pp.1764-1776
- Publisher
- Siam Publications
- DOI
- 10.1137/050627472
- ISSN
- 0097-5397
- eISSN
- 1095-7111
- Number of pages
- 13
- Language
- English
- Date published
- 01/01/2007
- Academic Unit
- Computer Science
- Record Identifier
- 9984259414002771
Metrics
6 Record Views