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

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

1. Proche Contexte plus large Pas pertinent

   Exponential improvements in Rado's covering problem

   G. 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…

2. Proche Contexte plus large Pas pertinent

   Local Optimality of the d-cube for Laplacian Eigenvalues

   Braxton 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. …

3. Proche Contexte plus large Pas pertinent

   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…

4. Proche Contexte plus large Pas pertinent

   Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls

   Hai-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…

5. Proche Contexte plus large Pas pertinent

   Hyperbolic intersection graphs and (quasi)-polynomial time

   Sá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…

6. Proche Contexte plus large Pas pertinent

   Tusnády's problem and online two-sample thinning

   Yuhao 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.

7. Proche Contexte plus large Pas pertinent

   Sharp Antipode-Neighbor Bounds in Every Dimension

   Samuel 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…

8. Proche Contexte plus large Pas pertinent

   MINVO Basis: Finding Simplexes with Minimum Volume Enclosing Polynomial Curves

   Jesus 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,…