  Approximating convex bodies is a fundamental question in geometry and has a
wide variety of applications. Consider a convex body $K$ of diameter $\Delta$
in $\textbf{R}^d$ for fixed $d$. The objective is to minimize the number of
vertices (alternatively, the number of facets) of an approximating polytope for
a given Hausdorff error $\varepsilon$. It is known from classical results of
Dudley (1974) and Bronshteyn and Ivanov (1976) that
$\Theta((\Delta/\varepsilon)^{(d-1)/2})$ vertices (alternatively, facets) are
both necessary and sufficient. While this bound is tight in the worst case,
that of Euclidean balls, it is far from optimal for skinny convex bodies.
  A natural way to characterize a convex object's skinniness is in terms of its
relationship to the Euclidean ball. Given a convex body $K$, define its
\emph{volume diameter} $\Delta_d$ to be the diameter of a Euclidean ball of the
same volume as $K$, and define its \emph{surface diameter} $\Delta_{d-1}$
analogously for surface area. It follows from generalizations of the
isoperimetric inequality that $\Delta \geq \Delta_{d-1} \geq \Delta_d$.
  Arya, da Fonseca, and Mount (SoCG 2012) demonstrated that the diameter-based
bound could be made surface-area sensitive, improving the above bound to
$O((\Delta_{d-1}/\varepsilon)^{(d-1)/2})$. In this paper, we strengthen this by
proving the existence of an approximation with
$O((\Delta_d/\varepsilon)^{(d-1)/2})$ facets.

Computational Geometry