We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Thrifty Approximations of Convex Bodies by Polytopes.
- Authors
Barvinok, Alexander
- Abstract
Given a convex body containing the origin in its interior and a real number τ>1, we seek to construct a polytope P⊂C with as few vertices as possible such that C⊂τP. Our construction is nearly optimal for a wide range of d and τ. In particular, we prove that if C=−C, then for any 1>ϵ>0 and τ=1+ϵ one can choose P having roughly ϵ−d/2 vertices and for one can choose P having roughly d1/ϵ vertices. Similarly, we prove that if is a convex body such that −C⊂μC for some μ≥1, then one can choose P having roughly ((μ+1)/(τ−1))d/2 vertices provided (τ−1)/(μ+1)≪1.
- Subjects
APPROXIMATION theory; CONVEX bodies; CONVEX polytopes; BANACH spaces; INTEGERS
- Publication
IMRN: International Mathematics Research Notices, 2014, Vol 2014, Issue 16, p4341
- ISSN
1073-7928
- Publication type
Article
- DOI
10.1093/imrn/rnt078