Thrifty approximations of convex bodies by polytopes

2012/06/18 by Barvinok, Alexander · 1 citation
#52A20 #52A21 #52A27 #52B55 #Combinatorics (math.CO) #FOS: Mathematics #Functional Analysis (math.FA) #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1206.3993

Abstract

Given a convex body C in R^d containing the origin in its interior and a real number tau > 1 we seek to construct a polytope P in C with as few vertices as possible such that C in tau P. Our construction is nearly optimal for a wide range of d and tau. In particular, we prove that if C=-C then for any 1>epsilon>0 and tau=1+epsilon one can choose P having roughly epsilon^-d/2 vertices and for tau=sqrtepsilon d one can choose P having roughly d^1/epsilon vertices. Similarly, we prove that if C in R^d is a convex body such that -C in mu C for some mu > 1 then one can choose P having roughly ((mu+1)/(tau-1))^d/2 vertices provided (tau-1)/(mu+1) << 1.

Cited by

• Gaussian Multiplier Bootstrap Procedure for the κth Largest Coordinate of High-Dimensional Statistics

Related

• Fine approximation of convex bodies by polytopes
• Approximation of smooth convex bodies by random polytopes
• Approximating a convex body by a polytope using the epsilon-net theorem
• Best and random approximation of a convex body by a polytope
• The computational complexity of convex bodies