A concentration inequality for random polytopes, Dirichlet-Voronoi tiling numbers and the geometric balls and bins problem

DOI10.1007/S00454-020-00174-3MaRDI QIDQ2664110zbMATH OpenOpenAlexFDO

Authors Gil Kur, Steven D. Hoehner

Publication date 20 April 2021

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.00167

zbMATH Keywords

approximationconvex bodiesrandom polytopessphere coveringtiling

Mathematics Subject Classification ID

Random convex sets and integral geometry (aspects of convex geometry) (52A22) Approximation by convex sets (52A27) Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Tilings in (n) dimensions (aspects of discrete geometry) (52C22)

Abstract: Our main contribution is a concentration inequality for the symmetric volume difference of a $C^2$ convex body with positive Gaussian curvature and a circumscribed random polytope with a restricted number of facets, for any probability measure on the boundary with a positive density function. We also show that the Dirichlet-Voronoi tiling numbers satisfy $ext{div}_{n-1}=(2pie{)}^{-1}(n+lnn)+O(1)$, which improves a classical result of Zador by a factor of $o(n)$. In addition, we provide a remarkable open problem which is the natural geometric generalization of the famous and fundamental "balls and bins" problem from probability. This problem is tightly connected to the optimality of random polytopes in high dimensions.

Recommendations

• Concentration of random polytopes around the expected convex hull
• Large deviation probabilities for the number of vertices of random polytopes in the ball
• Random polytopes, convex bodies, and approximation
• On the approximation of a ball by random polytopes
• On some fundamental aspects of polyominoes on random Voronoi tilings
• On the geometry of random polytopes
• Random polytopes in a convex polytope, independence of shape, and concentration of vertices
• On a random convex hull in an n-ball

Cites work

• A note on coverings
• A remark on the Mahler conjecture: local minimality of the unit cube
• A simple proof of an estimate for the approximation of the Euclidean ball and the Delone triangulation numbers
• A theorem on transfer for convex bodies
• Alice and Bob Meet Banach
• Approximation of a ball by random polytopes
• Approximation of smooth convex bodies by random circumscribed polytopes
• Approximation of the Euclidean ball by polytopes
• Approximation of the Euclidean ball by polytopes with a restricted number of facets
• Asymptotic approximation of smooth convex bodies by general polytopes
• Asymptotic approximation of smooth convex bodies by polytopes
• Asymptotic estimates for best and stepwise approximation of convex bodies II
• Asymptotic quantization error of continuous signals and the quantization dimension
• Central limit theorems for random polytopes
• Central limit theorems for random polytopes in a smooth convex set
• Convergence of algorithms for reconstructing convex bodies and directional measures
• Convex Bodies The Brunn-MinkowskiTheory
• Convex bodies with minimal volume product in \(\mathbb{R}^ 2\)
• Covering a sphere with spheres
• Geometric tomography
• Geometry and topology for mesh generation
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3921380 (Why is no real title available?)
• scientific article; zbMATH DE number 17646 (Why is no real title available?)
• scientific article; zbMATH DE number 480245 (Why is no real title available?)
• scientific article; zbMATH DE number 1975229 (Why is no real title available?)
• scientific article; zbMATH DE number 1975233 (Why is no real title available?)
• scientific article; zbMATH DE number 2117213 (Why is no real title available?)
• scientific article; zbMATH DE number 3232102 (Why is no real title available?)
• scientific article; zbMATH DE number 3364397 (Why is no real title available?)
• scientific article; zbMATH DE number 2209717 (Why is no real title available?)
• scientific article; zbMATH DE number 3058525 (Why is no real title available?)
• New analysis of the sphere covering problems and optimal polytope approximation of convex bodies
• On the approximation of a ball by random polytopes
• On the Delone triangulation numbers
• Polygonal approximation of plane convex bodies
• Polytopal approximation bounding the number of \(k\)-faces
• Polytopes of maximal volume product
• Random coverings in several dimensions
• Random polytopes and the Efron-Stein jackknife inequality.
• Sharp concentration of random polytopes
• Symmetric Mahler's conjecture for the volume product in the \(3\)-dimensional case
• The amount of overlapping in partial coverings of space by equal spheres
• The Covering of n -Dimensional Space by Spheres
• The surface area deviation of the Euclidean ball and a polytope
• THE VOLUME OF RANDOM POLYTOPES CIRCUMSCRIBED AROUND A CONVEX BODY
• Volume approximation of convex bodies by inscribed polytopes

Cited in

(3)

• An intrinsic volume metric for the class of convex bodies in ℝn
• Asymptotic expected T$T$‐functionals of random polytopes with applications to Lp$L_p$ surface areas
• Approximation of the Euclidean ball by polytopes with a fixed number of k-faces

This page was built for publication: A concentration inequality for random polytopes, Dirichlet-Voronoi tiling numbers and the geometric balls and bins problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664110)