3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 30, 2014 at 17:46
  • 1
    $\begingroup$ Thanks, but this is exactly the survey I linked in the question ;) $\endgroup$
    – Adrien
    Jan 30, 2014 at 17:48
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 30, 2014 at 17:54
  • $\begingroup$ @Adrien: Ah, apologies, I (obviously) did not follow your link. $\endgroup$ Jan 30, 2014 at 18:22

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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?). $\endgroup$ Mar 11, 2014 at 4:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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