Approximating a convex body by a polytope using the epsilon-net theorem

2017/05/22 by Márton Naszódi, Naszódi, Márton · 1 citation
Computer Science · Mathematics · #52A20 #52A27 #Computational Geometry and Mesh Generation #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Metric Geometry (math.MG) #Point processes and geometric inequalities

paper · doi:10.48550/arxiv.1705.07754

openalex publication_date 2017/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Giving a joint generalization of a result of Brazitikos, Chasapis and Hioni and results of Giannopoulos and Milman, we prove that roughly \lceil (d)/((1-ϑ)^d)ln(1)/((1-ϑ)^d) \rceil points chosen uniformly and independently from a centered convex body K in \mathbb R^d yield a polytope P for which ϑ K⊆ P⊆ K holds with large probability. The proof is simple, and relies on a combinatorial tool, the ε-net theorem.

Cited by

• On the deterministic interior body of random polytopes

Related

• Fine approximation of convex bodies by polytopes
• Random points, convex bodies, lattices
• Thrifty approximations of convex bodies by polytopes
• Concentration of random polytopes around the expected convex hull
• Big convex polytopes or rich hyperplanes