# Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets

We denote by $$V(A)$$ the $$d$$-volume of any convex set $$A$$. Furthermore, given any two convex sets $$A,B\in\mathbb{R}^d$$, we denote by $$V_{A,B}$$ the $$d$$-volume of the symmetric difference $$V\left(A \triangle B\right)$$.

Question: How can we prove or disprove that, for all $$d$$-dimensional convex shape $$S$$, there exists a convex polytope $$P$$ satisfying simultaneously the following two properties?

• Given the constant $$\gamma\in (0,1)$$ independent of $$d$$, we have $$V_{S,P}\le \gamma V(S)$$

• The number of its $$(d-1)$$-dimensional facets $$\phi_P$$ grows at most polynomially in $$d$$.

• Did you check it for balls? Nov 5, 2022 at 18:05
• $V(S)$ is itself upper bounded by a constant independent of $d$, viz. $1$. So what stops you from taking $P=\varnothing$? Nov 5, 2022 at 18:45
• All right, thank you. Now I am curious how you prove that a ball can be approximated by a hypercube. Nov 5, 2022 at 20:09
• I didn’t say it wasn’t true, I was just asking. But now that I have thought about it, I do actually think it’s not true. Here’s my intuition: for large $d$, $d$-dimensional balls and $d$-dimensional hypercubes alike have most of their volume concentrated close to their boundaries. But no matter how you choose the ratio of their radii, the boundaries of a ball and a hypercube will have small intersection. (Actually, the ratio of the radii is clear a priori: the volume of a $d$-dimensional unit ball is only close to the volume of a hypercube if the latter has edge length about $\sqrt{\pi e/n}$.) Nov 5, 2022 at 21:14
• Here is a back-of-the-envelope calculation, somewhat similar to @EmilJeřábek's. Consider the unit ball $B$. The ball $(1+O(1/d))B$ has volume larger by an $1+O(1)$ factor. If a point on the surface of the ball is $\omega(1/\sqrt d)$ from any hyperplane tangency, then the radial distance to the enveloping polyhedron at that point is $1+\omega(1/d)$, so that most points on the surface should be within $O(1/\sqrt d)$ of a tangency. That is, the points of tangency should be $O(1/\sqrt d)$-dense. But then there are super-exponentially many points of tangency. Nov 6, 2022 at 1:13