Approximation of convex body by polytopes

Question

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$?

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.