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

http://arXiv.org/abs/1206.3993