Economical Convex Coverings and Applications
Sunil Arya, Guilherme Dias da Fonseca, David M. Mount · SIAM Journal on Computing · 2024
Abstract. 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 [Formula: see text] and [Formula: see text], a covering is a collection of convex bodies whose union covers [Formula: see text] such that a constant factor expansion of each body lies within an [Formula: see text] expansion of [Formula: see text]. Coverings have been employed in many applications, such as approximations for diameter, width, and [Formula: see text]-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 [Formula: see text] for general convex bodies in [Formula: see text]. In special cases, such as when the convex body is the [Formula: see text] unit ball, this bound has been improved to [Formula: see text]. 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 [Formula: see text] and an approximation parameter [Formula: see text], we show that there exists a polytope [Formula: see text] consisting of [Formula: see text] vertices (facets) such that [Formula: see text]. This bound is optimal in the worst case up to factors of [Formula: see text]. (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 [Formula: see text]-approximate CVP algorithm that works in any norm, with a running time of [Formula: see text] up to polynomial factors in the input size, and we obtain the fastest [Formula: see text]-approximation algorithm for integer programming. We also present a framework for constructing coverings of optimal size for any convex body (up to factors of [Formula: see text]).