  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)} /
\epsilon^{(n-1)/2}$ for general convex bodies in $\textbf{R}^n$. In special
cases, such as when the convex body is the $\ell_p$ unit ball, this bound has
been improved to $2^{O(n)} / \epsilon^{(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, 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)} / \epsilon^{(n-1)/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)} / \epsilon ^{(n-1)/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)}$).
