On approximating the radii of point sets in high dimensions

Let P be a set of n points in R^d. For any 1≤k≤d, the outer k-radius of P, denoted by R_k(P), is the minimum, over all (d-k) -dimensional fiats F, of max_p∈P d(p, F), where d(p, F) is the Euclidean distance between the point p and fiat F. We consider the scenario when the dimension d is not fixed and can be as large as n. Computing the various radii of point sets is a fundamental problem in computational convexity with many applications. The main result of this paper is a randomized polynomial time algorithm that approximates Rk (P) to within a factor of O√(log n·log d) for any 1≤k≤d. This algorithm is obtained using techniques from semidefinite programming and dimension reduction. Previously, good approximation algorithms were known only for the case k=1 and for the case when k=d-c for any constant c; there are polynomial time algorithms that approximate Rk(P) to within a factor of (1+ε), for any ε>0, when d-k is any fixed constant. On the other hand, some results from the mathematical programming community on approximating certain kinds of quadratic programs imply an O√(log n) approximation for R₁ (P), the width of the point set P. We also prove an inapproximability result for computing Rk (P), which easily yields the conclusion that our approximation algorithm performs quite well for a large range of values of k. Our inapproximability result for Rk (P) improves the previous known hardness result of Brieden, and is proved by improving the parameters in Brieden´s construction using basic ideas from PCP theory.