Approximating convex bodies is a fundamental question in geometry, which has a wide variety of applications. Given a convex body K in \(\mathbb {R}^d\) for fixed d, the objective is to minimize the number of facets of an approximating polytope for a given Hausdorff error \(\varepsilon \) . It is known that \(O(({{\,\textrm{diam}\,}}(K)/\varepsilon )^{(d-1)/2})\) facets suffice and are necessary for many instances, such as the Euclidean ball. However, this bound is far from optimal for “skinny” convex bodies. A natural way to characterize the skinniness of a convex object is in terms of its relationship to the Euclidean ball. Given a convex body K, its volume diameter \(\Delta _d(K)\) is defined to be the diameter of a Euclidean ball of the same volume as K. The surface diameter \(\Delta _{d-1}(K)\) is defined analogously for surface area. It follows from generalizations of the isoperimetric inequality that \({{\,\textrm{diam}\,}}(K) \ge \Delta _{d-1}(K) \ge \Delta _d(K)\) . Arya, da Fonseca, and Mount proved that the diameter-based bound could be made sensitive to the surface diameter, improving the above bound to \(O((\Delta _{d-1}(K)/\varepsilon )^{(d-1)/2})\) . In this paper, we strengthen this by proving the existence of an approximation with \(O((\Delta _d(K)/\varepsilon )^{(d-1)/2})\) facets. As a function of volume alone, this bound is tight up to constant factors. Our improvements arise from a combination of new ideas. We exploit known properties of the original body and its polar dual. In order to obtain a volume-sensitive bound, we explore the problem of computing a low-complexity polytope that is sandwiched between two given convex bodies. We show that this problem can be reduced to a covering problem involving a natural intermediate body based on the harmonic mean. Our proof relies on a geometric analysis of a relative notion of fatness involving these bodies.
