Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions
Abstract
We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball Bd⊂ℝd with relative symmetric-difference volume error at most ε∈(0,1). We show that the minimum vertex budget Nε(d) satisfies log Nε(d)asymp dlog(1+1/ε√d). In particular, exp(O(√d/ε)) vertices suffice for every ε∈(0,1) and all sufficiently large d. We also prove that achieving a fixed error ε∈(0,1) requires at least Ω(((1+ε)/2√ε)d−1) facets, an exponential number in d. We extend our vertex approximation result to Gaussian symmetric-difference error, and give a positive answer to the question of De, Nadimpalli, and Servedio about subexponential vertex complexity for approximating Euclidean balls. We also disprove a Macbeath-type extremality principle for unrestricted vertex approximation. Whereas the ball uniformly maximizes the inscribed approximation error among all convex bodies (Macbeath, 1951), we show that approximating the hypercube [−1,1]d to relative error ε, with δ:=1−ε, requires N≥δ/2exp(Ω(δ2d/log2(2/δ))) vertices whenever d≥16log(2/δ). Thus, when d is large, the cube is harder to approximate than the ball in this sense. Finally, we determine the sharp dimensional order of the classical Laguerre-Delone triangulation number, showing that ldeld−1=Θ(d−1/2) as d→∞. This improves both the upper bound of Ludwig, Schütt, and Werner and the lower bound of Böröczky by a factor of order √d. By classical asymptotic approximation theorems (Ludwig, 1999), this improvement applies to every convex body in ℝd with C2 boundary and positive Gaussian curvature.
Related
- Cutting a convex body into fat parts and approximating Euclidean distance by graph distances
- Non-convex polytopes realizing kissing contact graphs in dimensions 5-7
- Scaled boundary cubature scheme in higher dimensions: integration over polytopes and curved regions
- Non-uniform exponential growth and the decay of growth rates in growing dimensions
- A surprising generalization of the Möbius function
BibTeX
@misc{gorodzha2026approximating,
title = {{Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions}},
author = {Yegor Gorodzha and Steven Hoehner and Gil Kur},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34651},
eprint = {2610.34651},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34651},
}
RIS
TY - UNPB
TI - Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions
AU - Yegor Gorodzha
AU - Steven Hoehner
AU - Gil Kur
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.34651
UR - https://arxiv.org/abs/2610.34651
AB - We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball B_d⊂ℝ^d with relative symmetric-difference volume error at most ε∈(0,1). We show that the minimum vertex budget N_ε(d) satisfies log N_ε(d)asymp dlog(1+1/ε√d). In particular, exp(O(√d/ε)) vertices suffice for every ε∈(0,1) and all sufficiently large d. We also prove that achieving a fixed error ε∈(0,1) requires at least Ω(((1+ε)/2√ε)^d−1) facets, an exponential number in d. We extend our vertex approximation result to Gaussian symmetric-difference error, and give a positive answer to the question of De, Nadimpalli, and Servedio about subexponential vertex complexity for approximating Euclidean balls. We also disprove a Macbeath-type extremality principle for unrestricted vertex approximation. Whereas the ball uniformly maximizes the inscribed approximation error among all convex bodies (Macbeath, 1951), we show that approximating the hypercube [−1,1]^d to relative error ε, with δ:=1−ε, requires N≥δ/2exp(Ω(δ^2d/log^2(2/δ))) vertices whenever d≥16log(2/δ). Thus, when d is large, the cube is harder to approximate than the ball in this sense. Finally, we determine the sharp dimensional order of the classical Laguerre-Delone triangulation number, showing that ldel_d−1=Θ(d^−1/2) as d→∞. This improves both the upper bound of Ludwig, Schütt, and Werner and the lower bound of Böröczky by a factor of order √d. By classical asymptotic approximation theorems (Ludwig, 1999), this improvement applies to every convex body in ℝ^d with C^2 boundary and positive Gaussian curvature.
ER -