Abstract
Let P be a set of n points in \mathbb{R}^d. For any 1 \leqslant k \leqslant d, the outer k-radius of P, denoted by Rk (P), is the minimum, over all (d - k)-dimensional flats F, of \max _{p\varepsilon P} d(p,f), where d (p, F) is the Euclidean distance between the point p and flat 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 0(\sqrt {\log n \cdot \log d}) for any 1 \leqslant k \leqslant d. This algorithm is obtained using techniques from semidefinite programming and dimension reduction. Previously, good approximation algorithms were known only for the case k =1and 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 + \varepsilon), for any e>0, when d - k is any fixed constant [23, 7]. On the other hand, some results from the mathematical programming community on approximating certain kinds of quadratic programs [28, 27] imply an 0(\sqrt {\log n} ) approximation for R1(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 [13], and is proved by improving the parameters in Brieden?s construction using basic ideas from PCP theory.