A Concentration Inequality for Random Polytopes, Dirichlet-Voronoi Tiling Numbers and the Geometric Balls and Bins Problem
arXiv:1801.00167 · doi:10.1007/s00454-020-00174-3
Abstract
Our main contribution is a concentration inequality for the symmetric volume difference of a 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 , which improves a classical result of Zador by a factor of . 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.
arXiv commentTypos, journal ref
References in corpus (6)
- A remark on the Mahler conjecture: local minimality of the unit cube
- Convergence of algorithms for reconstructing convex bodies and directional measures
- Learning Multivariate Log-concave Distributions
- The Surface Area Deviation of the Euclidean Ball and a Polytope
- The volume of random polytopes circumscribed around a convex body
- Approximation of the Euclidean ball by polytopes with a restricted number of facets