Approximating the radii of point sets

Kasturi Varadarajan; S. Venkatesh; Yinyu Ye; Jiawei Zhang

doi:10.1137/050627472

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.

Approximating the radii of point sets

View Online

Abstract

Details

Metrics