Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions

We determine the sharp dimensional dependence of the asymptotic approximation error for the Euclidean unit ball B₂ᵈᵈ by polytopes with a prescribed number of vertices in the relative symmetric difference metric. Specifically, we prove that limN→∞N2/(d-1)infP∈ Pd(N)vold(P B₂ᵈ)/vold(B₂ᵈ)=Θ(d-1/2), where Pd(N) consists of polytopes with at most N vertices and no containment restriction. Equivalently, the classical Laguerre-Delone triangulation numbers satisfy ldeld-1=Θ(d-1/2). This improves the lower bound Ω(d⁻¹) of Böröczky (2000) and the upper bound $O(1)$ of Ludwig, Schütt and Werner (2006). In contrast, the corresponding asymptotic coefficient for approximation with a prescribed number of facets has order one, as shown by Kur (2020). We also establish non-asymptotic bounds showing that, for every fixed ε∈(0,1), the ball admits an ε-approximation with at most exp(C(ε)√ d) vertices, whereas approximating the hypercube to the same accuracy requires at least exp(c(ε)d) vertices. Consequently, the ball does not maximize the optimal relative approximation error among convex bodies, even up to an absolute multiplicative constant at the same vertex budget. Thus Macbeath's theorem (1951) on the extremality of the ball for inscribed approximation does not extend to polytopes in arbitrary position.