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

Yegor Gorodzha; Steven Hoehner; Gil Kur

AI summary · arXiv: 2610.34651v2 · math.MG

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

Yegor Gorodzha, Steven Hoehner, Gil Kur

Original paper Submitted to arXiv on 26 Oct. 2026 71 pages, 1 figure, 1 table. v2: exposition and references revised for a broader audience License: NONEXCLUSIVE-DISTRIB 1.0 Also in: fr

How to read this summary? Illustrated guide

The essentials

Unrestricted vertex approximation of the Euclidean ball needs about exp(d log(1 + 1/(ε√d))) vertices, while fixed-error facet approximation remains exponential in dimension.

Question

How many vertices are required to approximate the Euclidean ball in high dimensions by a polytope under relative symmetric-difference volume error, when vertices may lie outside the ball? The paper also compares vertex and facet complexity and investigates whether the ball is extremal among convex bodies.

Method

The authors establish matching upper and lower bounds for the minimum vertex budget, using a dilated convex hull of independent uniform antipodal points on the sphere for the upper bound and simplex estimates with spherical-cap covering arguments for the lower bound. They also prove a vertex lower bound for the cube and analyze fixed-dimensional asymptotic approximation coefficients through a local simplex inequality and random-polytope methods.

Findings

Result For sufficiently large dimension and sufficiently small error, the logarithm of the minimum vertex budget is comparable to d log(1 + 1/(ε√d)).
See the passage in the paper
cd\log\left(1+\frac{1}{\varepsilon\sqrt{d}}\right)\leq\log N_{\varepsilon}(d)\leq Cd\log\left(1+\frac{1}{\varepsilon\sqrt{d}}\right).
Result At every fixed relative error, the ball can be approximated with exp(Θε(√d)) vertices, whereas approximating it with facets requires exp(Θε(d)) facets.
See the passage in the paper
At any fixed relative volume error $\varepsilon\in(0,1)$, we show that $\exp(\Theta_{\varepsilon}(\sqrt{d}))$ vertices are both necessary and sufficient, whereas $\exp(\Theta_{\varepsilon}(d))$ facets are required [56].
Result The hypercube requires exponentially many vertices at fixed error, showing that the ball does not maximize unrestricted vertex-approximation difficulty across convex bodies.
See the passage in the paper
Already the hypercube $[-1,1]^{d}$ provides a counterexample: Theorem 3 proves that for every fixed $\varepsilon\in(0,1)$ and all sufficiently large $d$, any polytope $P\in\mathcal{P}_{d}(N)$ with $\Delta_{[-1,1]^{d}}(P)\leq\varepsilon$ must have at least $\exp(c_{\varepsilon}d)$ vertices, regardless of where its vertices are placed.
Result The Laguerre–Delone triangulation number has order d^(-1/2), sharpening the dimensional dependence in classical asymptotic approximation results.
See the passage in the paper
In Theorem 4, we prove that $\mathcal{E}_{d}=\Theta(d^{-1/2})$, which also determines the dimensional order of the Laguerre–Delone triangulation number $\ldel_{d-1}$.
Authors’ interpretation The authors attribute the ball's low vertex complexity to radial and tangential fluctuation cancellation in their random-polytope construction.
See the passage in the paper
By analyzing the exact distribution of a random point on the boundary of this construction, we find that a cancellation between its radial and tangential fluctuations allows for subexponential budgets.

Limitations

The paper leaves open whether subexponential vertex complexity is possible for broader classes of convex bodies; its general upper bound for worst-case bodies remains larger than its cube-based lower bound.
See the passage in the paper
Together with our cube obstruction, this leaves a gap between $\exp(\Omega_{\varepsilon}(d))$ and $\exp(O_{\varepsilon}(d\log d))$ for worst-case unrestricted vertex approximation. Whether $\exp(O_{\varepsilon}(d))$ suffices for every convex body remains a natural question.
The precise leading constant in the asymptotic vertex coefficient is not determined; the paper provides lower and upper bounds.

Why it matters

The results show that vertex and facet descriptions can have substantially different complexity for volume approximation: the ball admits subexponential vertex budgets at fixed error even though facet budgets are exponential. The authors argue that the new simplex-based analysis also sharpens universal asymptotic approximation rates for smooth convex bodies and overturns a ball-extremality expectation for unrestricted vertex approximation.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Polytope approximation; symmetric-difference volume; random polytopes; vertex and facet complexity; high-dimensional convex geometry

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

The paper studies how many vertices or facets are required for a polytope to approximate a high-dimensional Euclidean unit ball when error is measured by the relative volume of the symmetric difference. Unlike containment- or distance-based measures, this criterion allows the polytope to extend beyond the ball. The central finding is that this freedom leads to sharply different behavior for vertex and facet descriptions. For vertex approximation, the minimum number of vertices $N$ needed to achieve error at most $\varepsilon$ satisfies \[ \log N \asymp d\log\!\left(1+\frac{1}{\varepsilon\sqrt d}\right), \] up to absolute constant factors. This estimate holds uniformly across accuracy regimes for sufficiently small $\varepsilon$, and the upper bound holds for every $0<\varepsilon<1$. In particular, at any fixed error, the required number of vertices is exponential in $\sqrt d$, rather than in $d$. The authors also prove that the optimal error achievable with $N$ vertices is at least a constant times $d^{-1/2}N^{-2/(d-1)}$. For sufficiently large exponential budgets, their upper bound matches this rate up to an absolute constant. Their construction takes the convex hull of independent uniform random points on the sphere together with their antipodes, then dilates the hull to balance its expected volume with that of the ball. A key technical step is an exact description of the distribution of a randomly selected boundary point, with selection probabilities weighted by the volumes of the cones beneath the facets. This separates fluctuations in facet height from fluctuations within each facet. The authors show that the interaction between these fluctuations keeps radial variation small enough for accurate volume approximation, even though some vertices lie far outside the ball. For the lower bound, the authors triangulate the polytope boundary and prove a local inequality showing that affine adjustments cannot eliminate the error incurred when approximating a quadratic surface over a simplex. They then use an anti-concentration inequality to translate this local error into a spherical-cap covering requirement. Covering at least half the sphere forces the stated lower bound on the number of vertices. The contrast with facet approximation is sharp: for every fixed error strictly between zero and one, an exponential number of facets in the dimension is both necessary and sufficient. The paper also extends the vertex upper bound to Gaussian symmetric-difference error. A single origin-symmetric polytope, with logarithmic vertex count at most a constant times $d\log(1+1/(\varepsilon\sqrt d))$, works for every centered ball and, more generally, for radially symmetric probability densities that decrease with distance from the origin. The authors challenge an expected extremality principle by showing that the cube is harder than the ball to approximate using unrestricted vertex descriptions. At fixed error $\varepsilon$, any polytope approximating the cube requires exponentially many vertices. The explicit lower bound has an exponent proportional to $d$ divided by the square of a quantity depending on $1-\varepsilon$ and its logarithm. The obstruction also extends to certain smooth bodies approximating the cube, so it cannot be attributed solely to the cube’s corners. Finally, the paper sharpens high-dimensional asymptotic approximation constants. It establishes that the Laguerre–Delone triangulation number has order $d^{-1/2}$, improving earlier dimensional bounds by a factor of order $\sqrt d$. The proof combines a simplex-level dual certificate that cancels every affine correction with the random-polytope analysis. The results do not determine exact optimal constants: the asymptotic bounds retain a constant-factor gap, and whether the random construction is optimal remains open.

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

How many corners does a polytope need to imitate a high-dimensional ball? The answer depends on what “imitate” means. If accuracy is measured by the relative volume of the parts where the polytope and ball differ, the polytope is allowed to stick out beyond the ball. That freedom changes the picture dramatically—and makes vertices and facets behave very differently.

In “Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions,” Yegor Gorodzha, Steven Hoehner, and Gil Kur study these questions across dimensions and levels of accuracy. Their results show that a ball can be approximated with far fewer vertices than familiar distance-based measures might suggest, while other shapes, including the cube, can be much more demanding.

Why volume difference changes the problem

Many approximation problems require a polytope to contain the ball, fit inside it, or remain close to its boundary at every point. This paper uses a different yardstick: the relative volume of the symmetric difference, the region belonging to one shape but not the other. A polytope can therefore extend outside the ball in some directions, as long as the total volume mismatch stays small.

This is not just a technical change. A few vertices can reach far beyond the ball while most of the polytope remains close to it. The results capture how that trade-off can be useful rather than automatically counting every outward excursion as a failure.

Vertex counts: a surprising high-dimensional rate

Let N be the number of vertices and let ε be the allowed volume error. The paper’s central estimate says that, for sufficiently small ε, the minimum vertex count obeys

log N ≍ d log(1 + 1/(ε√d)),

up to absolute constant factors. The upper bound applies throughout the full range 0 < ε < 1. One striking implication is that, at any fixed error, the required number of vertices grows exponentially in √d, rather than exponentially in the full dimension d.

The authors also establish a lower bound on the best possible error with N vertices: it is at least a constant times d-1/2N-2/(d-1). For sufficiently large exponential vertex budgets, their construction achieves the same rate up to an absolute constant. The bounds do not identify the exact optimum, but they show that the construction gets the dependence on dimension and vertex count essentially right.

How the random construction works

The construction starts by choosing independent random points uniformly from the sphere, adding the antipodes of those points, and taking their convex hull. The resulting polytope is then dilated so that its expected volume balances the volume of the ball.

Some vertices of this random polytope can lie far outside the ball. The key is that the overall radial variation can still remain small. To show why, the authors describe exactly how a random point on the polytope’s boundary is selected: facets are weighted by the volumes of the cones beneath them. This perspective separates variation in facet heights from variation within a facet. The interaction between those two sources of variation is controlled well enough to yield accurate volume approximation.

Why many vertices are sometimes unavoidable

The lower-bound argument examines the polytope boundary piece by piece. After triangulating that boundary, the authors prove a local inequality: even when an affine adjustment is allowed, it cannot erase the error involved in using a simplex to approximate a quadratic surface.

They then turn this local geometric error into a covering problem on the sphere using an anti-concentration inequality. If the approximation error is small, the simplices must account for a substantial portion of the sphere; covering at least half of it forces the stated lower bound on the number of vertices.

Facets, Gaussian error, and the cube

Facet descriptions tell a very different story. For every fixed error strictly between zero and one, approximating the ball requires—and can be done with—an exponential number of facets in the dimension. Thus the advantage of allowing a polytope to extend beyond the ball does not make vertex and facet descriptions interchangeable.

The vertex upper bound also extends beyond uniform volume comparison. The authors show that one origin-symmetric polytope can work for every centered ball and, more broadly, for radially symmetric probability densities that decrease with distance from the origin. Its logarithmic vertex count is at most a constant times d log(1 + 1/(ε√d)).

The paper also challenges the idea that the ball must be the hardest body to approximate. For a cube, any polytope achieving a fixed error needs exponentially many vertices. The explicit lower bound has an exponent proportional to the dimension divided by the square of a quantity involving 1 − ε and its logarithm. Related obstructions persist for certain smooth bodies that approximate the cube, so the difficulty is not simply a consequence of the cube’s sharp corners.

What remains open

Finally, the authors improve a high-dimensional asymptotic constant: the Laguerre–Delone triangulation number has order d-1/2, a factor of order √d sharper than earlier dimensional bounds. Their proof combines a simplex-level dual certificate, which cancels affine corrections, with the random-polytope analysis.

The results leave an important question unresolved: are the random polytopes optimal, or can another construction do better? The upper and lower estimates still differ by a constant factor, so the exact optimal constants remain unknown. Even so, the paper makes a compelling point: under volume-based error, high-dimensional geometry can reward a surprisingly loose fit—and the number of corners needed depends profoundly on the shape being approximated.

Created on 09 Nov. 2026

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Weekly letter Presented in "Mathematics and statistics this week" of 9 November 2026. Mathematics and statistics this week: Where geometry sets the limits

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Papers around this one

See them on a map

Ranked by how close their title and abstract are to this paper’s. Select some to read them together.

Closest papers

Close Broader context
Exponential improvements in Rado's covering problem
G. Dall'Ara, A. Dumitrescu · 2026 · Not summarized yet

Exponential improvements in Rado's covering problem bounds disjoint volume coverage by unit Euclidean balls, rather than approximating a ball by a polytope.

Abstract
Let $B^d$ denote the $d$-dimensional Euclidean ball of unit radius. What is the largest constant $f(B^d) \in [0,1]$ with the property that every finite collection $\mathcal{C}$ of unit balls in $\mathbb{R}^d$ admits a disjoint sub-collection $\mathcal{S}$ occupying at least a fraction $f(B^d)$ of the volume of $\mathcal{C}$? This problem was first raised by T. Rad\'o in 1928, for axis-parallel squares in the plane; the author was motivated by a classical covering lemma in real analysis due to Vitali. The case of Euclidean balls was first considered by R. Rado in 1949. Until last year the best known estimates on $f(B^d)$ for unit balls where very far apart: \[ (1+\epsilon_d) 3^{-d} \leq f(B^d…
Close Broader context
Local Optimality of the d-cube for Laplacian Eigenvalues
Braxton Osting, Robert Viator · 2026 · Not summarized yet

Local Optimality of the d-cube for Laplacian Eigenvalues studies cube shape and spectral properties, not its vertex complexity for volume approximation.

Abstract
For each $d \ge 2$ we prove that the unit $d$-cube $\square_d \subset \mathbb{R}^d$ is, on the class $\mathcal{P}$ of convex polytopes combinatorially equivalent to a $d$-cube, (i) a strict local minimizer of the scale-invariant isoperimetric ratio $I(\Omega) = \tfrac{P(\Omega)^d}{|\Omega|^{d-1}}$, with $P$ the perimeter, (ii) a strict local minimizer of the volume-normalized first Dirichlet eigenvalue $\bar\lambda(\Omega) = |\Omega|^{2/d}\lambda_1(\Omega)$, and (iii) a strict local maximizer of the volume-normalized first Neumann eigenvalue $\bar\mu(\Omega) = |\Omega|^{2/d}\mu_1(\Omega)$. The method is a shape-derivative Hessian analysis adapted to the hyperoctahedral symmetry of the cube. …
Close Broader context
Quasipolynomial density bounds for $K$-point configurations in $\mathbb{Z}^d$
Andrew Lott, Á. Magyar, N. R. Ponagandla · 2026 · Not summarized yet

Quasipolynomial density bounds for K-point configurations in Z^d uses simplex geometry in a density problem, not polytope approximation of the ball.

Abstract
Let $d,K,N\in \mathbb{N}$ with $K\geq 3$ and $d\geq 4K+4$. Let $\Delta\subset \mathbb{Z}^d$ be the vertex set of a nondegenerate $(K-1)$-simplex, and let $A\subseteq[N]^d$ contain no nontrivial similar copy of $\Delta$. We prove that \[ |A|\ll_{\Delta,d} N^d\exp\!\left(-c_{\Delta,d}\sqrt{\log N}\right) \] improving upon a polylogarithmic bound due to Magyar. We perform a density increment argument using the circle method, and we introduce a ``cut operator''method to decouple the weighted exponential sum over the system of quadratic forms describing the simplex. Our proof combines ideas from graph theory, functional analysis, and the geometry of numbers. In the process, we apply Finner's frac…
Close Broader context
Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls
Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 2026 · cited 3 times · Not summarized yet

Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls studies query complexity on a ball, not geometric approximation by polytopes.

Abstract
We prove a joint stochastic zeroth-order lower bound for Goldstein stationarity on a Euclidean query ball, even when the ball is guaranteed to contain a stationary point. In dimension $d$, let $f=\mathbb{E}[F(\cdot;\xi)]$, assume $\mathbb{E}[\operatorname{Lip}(F(\cdot;\xi))^2]\le L_0^2$, and bound the initial objective gap over the ball by $\Delta$. For neighborhood radius $\delta>0$ and residual tolerance $\varepsilon>0$, our smooth hard family requires $\Omega(dL_0^2\Delta/(\delta\varepsilon^3))$ scalar evaluations for success probability $1/2$, against randomized adaptive algorithms that may retain and repeatedly query each sampled function. The result holds for $\varepsilon\le cL_0$, $\D…
Close Broader context
Hyperbolic intersection graphs and (quasi)-polynomial time
Sándor Kisfaludi-Bak · 2018 · Computational Geometry · cited 23 times · AI summary available

Hyperbolic intersection graphs and (quasi)-polynomial time studies ball graphs and algorithms in hyperbolic space, not Euclidean-ball approximation.

Abstract
We study unit ball graphs (and, more generally, so-called noisy uniform ball graphs) in $d$-dimensional hyperbolic space, which we denote by $\mathbb{H}^d$. Using a new separator theorem, we show that unit ball graphs in $\mathbb{H}^d$ enjoy similar properties as their Euclidean counterparts, but in one dimension lower: many standard graph problems, such as Independent Set, Dominating Set, Steiner Tree, and Hamiltonian Cycle can be solved in $2^{O(n^{1-1/(d-1)})}$ time for any fixed $d\geq 3$, while the same problems need $2^{O(n^{1-1/d})}$ time in $\mathbb{R}^d$. We also show that these algorithms in $\mathbb{H}^d$ are optimal up to constant factors in the exponent under ETH. This drop in d…
Close Broader context
Tusnády's problem and online two-sample thinning
Yuhao Lei · 2026 · Combinatorics · AI summary available

Tusnády's problem and online two-sample thinning uses geometric discrepancy for point sets, rather than vertex or facet bounds for approximating a ball.

In short
The paper establishes sharp discrepancy bounds for Tusnády’s problem and online thinning, including a separation between prefix and terminal objectives.
Close Broader context
Sharp Antipode-Neighbor Bounds in Every Dimension
Samuel Korsky · 2026 · cited 1 time · Not summarized yet

Sharp Antipode-Neighbor Bounds in Every Dimension studies distances between point pairs in bounded-diameter sets, not approximation of convex bodies.

Abstract
Let $P\subset\mathbb R^d$ be finite with $\operatorname{diam}(P)\le1$. For $0<\varepsilon<1$, let $\mathcal N_\varepsilon(P)$ denote the number of ordered pairs at distance at most $\varepsilon$, including the diagonal, and let $\mathcal A_\varepsilon(P)$ denote the number of ordered pairs at distance at least $1-\varepsilon$. We prove the sharp bound \[ \mathcal N_\varepsilon(P)\gtrsim_d \varepsilon^{(d-1)/2}\mathcal A_\varepsilon(P) \] conjectured by Steinerberger (2025). More generally, the same inequality holds for finite positive Borel measures. The main input is a uniform $L^2$ estimate, at cap thickness comparable to lattice spacing, for a supporting-direction incidence operator. In g…
Close Broader context
MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves
Jesus Tordesillas, Jonathan P. How · 2020 · Computational Geometry · cited 50 times · AI summary available

MINVO Basis finds minimum-volume simplices enclosing polynomial curves, whereas this paper bounds vertex counts for volume approximation of the Euclidean ball.

Abstract
Outer polyhedral representations of a given polynomial curve are extensively exploited in computer graphics rendering, computer gaming, path planning for robots, and finite element simulations. Bézier curves (which use the Bernstein basis) or B-Splines are a very common choice for these polyhedral representations because their non-negativity and partition-of-unity properties guarantee that each interval of the curve is contained inside the convex hull of its control points. However, the convex hull provided by these bases is not the one with smallest volume, producing therefore undesirable levels of conservatism in all of the applications mentioned above. This paper presents the MINVO basis,…

Go further

How are these papers found?

We compare the title and abstract of this paper with those of every paper summarized on this site, and with the papers Semantic Scholar recommends, those it cites and those citing it (for a much-cited paper, its most recent citations and, from OpenAlex, the most cited ones). Among the prior work and the follow-ups, the papers that use each other in depth, a method it uses and the much-cited follow-ups come a little higher. The levels (very close, close, related) come from the similarity of the texts, not from a judgment of quality; * marks a paper without an abstract, compared by its title. The sentence under a paper is written by an AI from the two abstracts: check it in the papers. A paper marked not relevant by three readers leaves the list.

Updated on 9 November 2026.

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.

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

The essentials

Question

Method

Findings

Limitations

Why it matters

Read further

Definitions

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

Why volume difference changes the problem

Vertex counts: a surprising high-dimensional rate

How the random construction works

Why many vertices are sometimes unavoidable

Facets, Gaussian error, and the cube

What remains open

Ask questions about this paper to our AI assistant

Tools for this paper

Advanced tools Premium

Papers around this one

Closest papers

Go further

Cite this paper (BibTeX)