← 研踪 PaperTrailarXiv:2610.34651 · v2
Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions
首次提交 2026-10-26 08:29
版本更新 2026-11-04 05:52
雷达观测 2026-11-06 11:07
摘要
We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball $B_d\subset\mathbb R^d$ with relative symmetric-difference volume error at most $\varepsilon\in(0,1)$. We show that the minimum vertex budget $N_\varepsilon(d)$ satisfies $$\log N_\varepsilon(d)\asymp d\log\left(1+\frac1{\varepsilon\sqrt d}\right).$$ In particular, $\exp(O(\sqrt d/\varepsilon))$ vertices suffice for every $\varepsilon\in(0,1)$ and all sufficiently large $d$. We also prove that achieving a fixed error $\varepsilon\in(0,1)$ requires at least $Ω\bigl((\tfrac{1+\varepsilon}{2\sqrt\varepsilon})^{d-1}\bigr)$ 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 $\varepsilon$, with $δ:=1-\varepsilon$, requires $N\ge\fracδ{2}\exp(Ω(δ^2d/\log^2(2/δ)))$ vertices whenever $d\ge16\log(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 $\mathrm{ldel}_{d-1}=Θ(d^{-1/2})$ as $d\to\infty$. 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 $\sqrt d$. By classical asymptotic approximation theorems (Ludwig, 1999), this improvement applies to every convex body in $\mathbb R^d$ with $C^2$ boundary and positive Gaussian curvature.
作者备注：71 pages, 1 figure, 1 table. v2: exposition and references revised for a broader audience
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-04 05:52 · 最新观测版本
Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions
We provide sharp estimates on the number of vertices needed to approximate the Euclidean unit ball $B_d\subset\mathbb R^d$ with relative symmetric-difference volume error at most $\varepsilon\in(0,1)$. We show that the minimum vertex budget $N_\varepsilon(d)$ satisfies $$\log N_\varepsilon(d)\asymp d\log\left(1+\frac1{\varepsilon\sqrt d}\right).$$ In particular, $\exp(O(\sqrt d/\varepsilon))$ vertices suffice for every $\varepsilon\in(0,1)$ and all sufficiently large $d$. We also prove that achieving a fixed error $\varepsilon\in(0,1)$ requires at least $Ω\bigl((\tfrac{1+\varepsilon}{2\sqrt\varepsilon})^{d-1}\bigr)$ 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 $\varepsilon$, with $δ:=1-\varepsilon$, requires $N\ge\fracδ{2}\exp(Ω(δ^2d/\log^2(2/δ)))$ vertices whenever $d\ge16\log(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 $\mathrm{ldel}_{d-1}=Θ(d^{-1/2})$ as $d\to\infty$. 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 $\sqrt d$. By classical asymptotic approximation theorems (Ludwig, 1999), this improvement applies to every convex body in $\mathbb R^d$ with $C^2$ boundary and positive Gaussian curvature.
查看此版本解读 →查看此版本原文 ↗