Approximation of the Euclidean ball by polytopes with a restricted number of facets

Abstract

We prove that there is an absolute constant $C$ such that for every $n\ge 2$ and $N\ge 10^n,$ there exists a polytope $P_{n,N}\subset {\mathbb{R}}^n$ with at most $N$ facets that satisfies $${\Delta }_v(D_n,P_{n,N}):={\text{vol}}_n\left(D_n\Delta P_{n,N}\right)\le C{n}^{-2/(n-1}{\text{vol}}_n\left(D_n\right)$$ and $${\Delta }_s(D_n,P_{n,N}):={\text{vol}}_{n-1}\left(\partial \left(D_n\cup P_{n,N}\right)\right)-{\text{vol}}_{n-1}\left(\partial \left(D_n\cap P_{n,N}\right)\right)\le 4C{N}^{-\frac{2}{n-1}}{\text{vol}}_{n-1}\left(\partial D_n\right),$$ where $D_n$ is the $n$-dimensional Euclidean unit ball. This result closes gaps from several papers of Hoehner, Ludwig, Schütt and Werner. The upper bounds are optimal up to absolute constants. This result shows that a polytope with an exponential number of facets (in the dimension) can approximate the $n$-dimensional Euclidean ball with respect to the aforementioned distances.

References in corpus (1)

• The Surface Area Deviation of the Euclidean Ball and a Polytope

Cited by in corpus (3)

• Optimality of Maximum Likelihood for Log-Concave Density Estimation and Bounded Convex Regression
• A Concentration Inequality for Random Polytopes, Dirichlet-Voronoi Tiling Numbers and the Geometric Balls and Bins Problem
• An intrinsic volume metric for the class of convex bodies in ${\mathbb{R}}^n$