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 $\epsilon >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 $\epsilon$ expansion of $K$. Coverings have been employed in many applications, such as approximations for diameter, width, and $\epsilon$-kernels of point sets, approximate nearest neighbor searching, polytope approximations, and approximations to the Closest Vector Problem (CVP). It is known how to construct coverings of size $n^{O(n)}\mathrm{/}{\epsilon }^{(n-1)\mathrm{/}2}$ for general convex bodies in ${\mathbf{\text{R}}}^n$. In special cases, such as when the convex body is the ${\mathrm{\ell }}_p$ unit ball, this bound has been improved to $2^{O(n)}\mathrm{/}{\epsilon }^{(n-1)\mathrm{/}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, under the Banach-Mazur metric. Given a well-centered convex body $K$ and an approximation parameter $\epsilon >0$, we show that there exists a polytope $P$ consisting of $2^{O(n)}\mathrm{/}{\epsilon }^{(n-1)\mathrm{/}2}$ vertices (facets) such that $K\subset P\subset K(1+\epsilon )$. This bound is optimal in the worst case up to factors of $2^{O(n)}$. As an additional consequence, we obtain the fastest $(1+\epsilon )$-approximate CVP algorithm that works in any norm, with a running time of $2^{O(n)}\mathrm{/}{\epsilon }^{(n-1)\mathrm{/}2}$ up to polynomial factors in the input size, and we obtain the fastest $(1+\epsilon )$-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)}$).