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 R_k (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 R_k(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 R_k(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 R₁(P), the width of the point set P.

We also prove an inapproximability result for computing R_k(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 R_k(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.