Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This question deals with approximating a convex body (a compact convex set of $\mathbb{R}^d$ with non-empty interior) by convex polytopes.

For a given $\delta$, let $n_\delta$ be the number of faces needed to approximate any convex body by a contained convex polytope with at most $n_\delta$ faces and Hausdorff distance at most $\delta$. I'm interested in non-asymptotic upper-bounds on this number $n_\delta$ of faces.

In the following survey: http://link.springer.com/article/10.1007/s10958-008-9144-x, the author gives in (6) a non asymptotic upper bound, on the number of vertices $n_{\delta,v}$ needed to approximate a convex body by a polytope with Hausdorff distance at most $\delta$: $$\delta \leq \frac{C}{n_{\delta,v}^{\frac{2}{d-1}}} $$ He then states "Certainly the same estimates hold for" approximation by polytopes contained in/containing the convex body, and also replacing vertices by faces.

So when taking "faces" and "contained in", this is exactly the result I want. Unfortunately, there is no clear reference given to such results.

Since this problem is really far from my field, I don't have access to many sources through my department's subscriptions to scientific journals and through my libray. If I knew a precise reference, it would be no problem for me to ask my department to purchase the precise reference or my library to borrow the precise book, but it is very difficult for me to find such a precise reference.

So I'd be very grateful if anyone could point a precise reference to this result out to me.

share|improve this question
1  
This fairly recent survey (which I have not accessed) may help: E.M. Bronshtein, "Approximation of convex sets by polyhedra," J. Math. Sci. (N.Y.) 153 (2008), no.6, 727--762. –  Joseph O'Rourke Jan 30 at 17:46
    
Thanks, but this is exactly the survey I linked in the question ;) –  Adrien Jan 30 at 17:48
2  
The survey of Bronshtein lists over 200 articles in the references, many by Imre Bárány. You may want to look at them, or contact Bárány directly. His email address should be given in some of his articles. –  Wlodek Kuperberg Jan 30 at 17:54
    
@Adrien: Ah, apologies, I (obviously) did not follow your link. –  Joseph O'Rourke Jan 30 at 18:22

1 Answer 1

If you want to replace contained in by containing and vertices by facets, this should be just a matter of applying the Polar set operation (http://en.wikipedia.org/wiki/Polar_set). Polars (when the original set strictly contains the origin) reverse inclusion and convert facets to vertices, and vice-versa. I hope this helps

share|improve this answer
2  
And to replace "Hausdorff distance $\delta$" by "contained in and Hausdorff distance $\delta'$" one just needs to scale down the approximating polytope by an appropriate factor (which might include the outradius?). –  Yoav Kallus Mar 11 at 4:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.