In a recent survey paper, Approximation of convex sets by polytopes, Bronstein claims that under Hausdorff distance $\rho_H$, for every convex body $U$, $$\rho_H(U,\mathcal{P}_n)\leq c(U) n^{-2/(d-1)},$$ where $\mathcal{P}_n$ is the set of all polytopes with at most $n$ vertices. It is claimed in the survey paper (pp.729, section 4.1) that the same estimate is also valid if we replace $\mathcal{P}_n$ with other sets, including (1) $\mathcal{I}_n(U)$, the set of all inscribed polytopes in $U$ with at most $n$ vertices; (2) $\mathcal{I}_{(n)}(U)$, the set of all inscribed polytopes in $U$ with at most $n$ facets; (3)$\mathcal{O}_n(U)$, the set of all polytopes circumscribing $U$ with at most $n$ vertices, and (4) $\mathcal{O}_{(n)}(U)$, the set of all polytopes circumscribing $U$ with at most $n$ facets.

My questions are:

(1) Is there any result concerning the symmetric difference metric with the same estimate? In particular I am interested in the case $\mathcal{O}_{(n)}(U)$. An upper bound would be fine. Preferably with explicit constants such as $c_1\cdot c_2(d)c_3(U)$ with $c_2,c_3$ explicitly defined. No smoothness of the boundary is assumed and I am currently not interested too much about the asymptotic expansion the error estimate (usually involving the Gaussian curvature somewhere)

(2) Similarly, do we have results that give an estimate of how well can polyhedral functions can approximate (good) convex function on a fixed domain $\Omega$?

  • 2
    $\begingroup$ I think the following may interest you: projecteuclid.org/… See also other papers by the same author at: crest.fr/pagesperso.php?user=3299#publications $\endgroup$
    – Suvrit
    Mar 2 '15 at 19:33
  • 1
    $\begingroup$ [Symmetric difference distance]$(U,P)\le \mathrm{Const}(U)\cdot$[Hausdorff distance]$(U,P)$; hence the statement follows. $\endgroup$ Mar 2 '15 at 19:55
  • $\begingroup$ @Suvrit Thanks very much for turning my attention to the paper. In terms of estimation of convex set, there is some recent development. Aditya Gutunboyina from Berkeley is also one that should definitely keep track of. $\endgroup$
    – Roy Han
    Mar 2 '15 at 19:58
  • $\begingroup$ @AntonPetrunin Thanks for pointing this out. The thing is in the survey paper no reference concerning the proof for any case is mentioned. I'd really like to have some reference with a detailed proof. Preferrably with all constants explicit as in the asymptotic formula assuming $C^2$ boundary $\endgroup$
    – Roy Han
    Mar 2 '15 at 20:00

If by the "symmetric difference metric" you mean the Nikodym Metric, there are plenty of references in Section 4.2 in Bronstein's 2008 survey. In particular, very precise upper bounds for $\mathcal{P}_n = \mathcal{I}_n$ and lower bounds for $\mathcal{P}_n= \mathcal{O}_{(n)}$.

Regarding upper bounds for $\mathcal{P}_n = \mathcal{O}_{(n)}$, you could use [1, Section 5].

In that paper, Reisner, Schütt and Werner show that for any convex body $C$ in $\mathbb{R}^n$ such that $0 \in C$, there is a polytope $R \subset C$ of at most $N$ vertex such that $R$ approximates $C$ well (under the symmetric difference metric) and the polar $R^*$ approximates $C^*$ well (i.e. $error = O(N^{-2/(d-1)}$).

[1] S. Reisner, C. Schu ̈tt, and E. Werner. Dropping a vertex or a facet from a convex polytope. In Forum Math., volume 13, pages 359–378, 2001.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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