Approximating the Euclidean Ball by Polytopes: Surprising Rates in High Dimensions
Auteurs : Yegor Gorodzha, Steven Hoehner, Gil Kur
Résumé scientifique
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.
Les articles autour de lui, par date et par proximité
Plus haut, c’est plus proche de cet article ; à gauche, c’est plus ancien. Les traits relient les articles proches entre eux : les groupes de traits sont des sous-thèmes. Sélectionnez un point pour voir pourquoi il est là. Retour au résumé de cet article
Les articles autour de celui-ci
Classés selon la proximité de leur titre et de leur résumé avec ceux de cet article. Sélectionnez-en pour les lire ensemble.
Les articles les plus proches
-
Exponential improvements in Rado's covering problemG. Dall'Ara, A. Dumitrescu · 2026 · Pas encore résumé
« Exponential improvements in Rado's covering problem » étudie la fraction de volume couverte par des boules unitaires disjointes, et non l’approximation de la boule par des polytopes.
Résumé scientifique
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…
-
Local Optimality of the d-cube for Laplacian EigenvaluesBraxton Osting, Robert Viator · 2026 · Pas encore résumé
« Local Optimality of the d-cube for Laplacian Eigenvalues » analyse les valeurs propres et le rapport isopérimétrique du cube, plutôt que son approximation polyédrique.
Résumé scientifique
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. …
-
Quasipolynomial density bounds for $K$-point configurations in $\mathbb{Z}^d$Andrew Lott, Á. Magyar, N. R. Ponagandla · 2026 · Pas encore résumé
« Quasipolynomial density bounds for K-point configurations in Z^d » étudie des ensembles entiers évitant des copies de simplexes, sans traiter l’approximation des boules.
Résumé scientifique
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…
-
Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean BallsHai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 2026 · cité 3 fois · Pas encore résumé
« Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls » établit une borne de complexité d’optimisation sur une boule, non une borne d’approximation géométrique.
Résumé scientifique
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…
-
Hyperbolic intersection graphs and (quasi)-polynomial timeSándor Kisfaludi-Bak · 2018 · Computational Geometry · cité 23 fois · Résumé IA disponible
« Hyperbolic intersection graphs and (quasi)-polynomial time » étudie des graphes de boules en espace hyperbolique et la complexité d’algorithmes, non les polytopes approchant une boule.
Résumé scientifique
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…
-
Tusnády's problem and online two-sample thinningYuhao Lei · 2026 · Combinatorics · Résumé IA disponible
« Tusnády's problem and online two-sample thinning » établit des bornes de discordance pour des boîtes alignées et leur application à l’échantillonnage en ligne.
En bref
L’article établit des ordres optimaux de discrépance pour le problème de Tusnády et la sélection en ligne de deux échantillons, avec des résultats distincts pour les préfixes et les résultats terminaux.
-
Sharp Antipode-Neighbor Bounds in Every DimensionSamuel Korsky · 2026 · cité 1 fois · Pas encore résumé
« Sharp Antipode-Neighbor Bounds in Every Dimension » relie les paires proches et presque antipodales dans des ensembles de diamètre borné, plutôt que d’approximer une boule.
Résumé scientifique
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…
-
MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial CurvesJesus Tordesillas, Jonathan P. How · 2020 · Computational Geometry · cité 50 fois · Résumé IA disponible
« MINVO Basis » construit des simplexes de volume minimal contenant des courbes polynomiales, tandis que l’article étudie l’approximation de boules par des polytopes.
Résumé scientifique
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,…
Aller plus loin
Comment ces articles sont-ils trouvés ?
Nous comparons le titre et le résumé de cet article avec ceux de tous les articles résumés sur ce site, et avec les articles que Semantic Scholar recommande, ceux qu’il cite et ceux qui le citent (pour un article très cité, ses citations les plus récentes et, depuis OpenAlex, les plus citées). Parmi les travaux antérieurs et les suites, les articles qui s’utilisent en profondeur, une méthode qu’il utilise et les suites très citées remontent un peu. Les niveaux (très proche, proche, apparenté) viennent de la similarité des textes, pas d’un jugement de qualité ; * signale un article sans résumé, comparé par son titre. La phrase sous un article est écrite par une IA à partir des deux résumés : vérifiez-la dans les articles. Un article jugé hors sujet par trois lecteurs quitte la liste.
Mis à jour le 9 novembre 2026.