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
  • 3
    $\begingroup$ The paper you cite was published in 1975. This is not called "recent", IMHO... $\endgroup$ – Dima Pasechnik Mar 2 '15 at 19:48
  • 1
    $\begingroup$ [Symmetric difference distance]$(U,P)\le \mathrm{Const}(U)\cdot$[Hausdorff distance]$(U,P)$; hence the statement follows. $\endgroup$ – Anton Petrunin 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
  • 1
    $\begingroup$ @DimaPasechnik Thanks for pointing this out!! I meant to cite one survey published in 2008....I have already corrected it. $\endgroup$ – Roy Han Mar 2 '15 at 19:59

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.

| cite | improve this answer | |

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.