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, 2015 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, 2015 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, 2015 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, 2015 at 20:00

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .