Economical Convex Coverings and Applications

Coverings of convex bodies have emerged as a central component in the design of efficient solutions to approximation problems involving convex bodies. Intuitively, given a convex body K and ε > 0, a covering is a collection of convex bodies whose union covers K such that a constant factor expansion of each body lies within an ε expansion of K. Coverings have been employed in many applications, such as approximations for diameter, width, and ε-kernels of point sets, approximate nearest neighbor searching, polytope approximations with low combinatorial complexity, and approximations to the Closest Vector Problem (CVP).

It is known how to construct coverings of size n O(n) /ε (n-1)/2 for general convex bodies in R n . In special cases, such as when the convex body is the ℓ p unit ball, this bound has been improved to 2 O(n) /ε (n-1)/2 . This raises the question of whether such a bound generally holds. In this paper we answer the question in the affirmative.

We demonstrate the power and versatility of our coverings by applying them to the problem of approximating a convex body by a polytope, where the error is measured through the Banach-Mazur metric. Given a well-centered convex body K and an approximation parameter ε > 0, we show that there exists a polytope P consisting of 2 O(n) /ε (n-1)/2 vertices (facets) such that K ⊂ P ⊂ K(1 + ε). This bound is optimal in the worst case up to factors of 2 O(n) . (This bound has been established recently using different techniques, but our approach is arguably simpler and more elegant.) As an additional consequence, we obtain the fastest (1 + ε)-approximate CVP algorithm that works in any norm, with a running time of 2 O(n) /ε (n-1)/2 up to polynomial factors in the input size, and we obtain the fastest (1 + ε)-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of 2 O(n) ).