This is an announcement for the paper "Thrifty approximations of convex bodies by polytopes" by Alexander Barvinok.
Abstract: Given a convex body C in R^d we construct a polytope P in C with relatively few vertices which approximates C relatively well. In particular, we prove that if C=-C then for any 1>epsilon>0 to have P in C and C in (1+epsilon) P one can choose P having roughly epsilon^{-d/2} vertices and for P in C and C in sqrt{epsilon d} P 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 to have P in C and C in (1+epsilon)P one can choose P having roughly (mu/epsilon)^{d/2} vertices.
Archive classification: math.MG math.CO math.FA
Mathematics Subject Classification: 52A20, 52A27, 52A21, 52B55
Remarks: 13 pages
Submitted from: barvinok@umich.edu
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/1206.3993
or