7
$\begingroup$

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

Improve this question
$\endgroup$
18
  • 1
    $\begingroup$ Did you check it for balls? $\endgroup$
    – Anton Petrunin
    Commented Nov 5, 2022 at 18:05
  • 1
    $\begingroup$ $V(S)$ is itself upper bounded by a constant independent of $d$, viz. $1$. So what stops you from taking $P=\varnothing$? $\endgroup$
    – Emil Jeřábek
    Commented Nov 5, 2022 at 18:45
  • 2
    $\begingroup$ All right, thank you. Now I am curious how you prove that a ball can be approximated by a hypercube. $\endgroup$
    – Emil Jeřábek
    Commented Nov 5, 2022 at 20:09
  • 1
    $\begingroup$ 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}$.) $\endgroup$
    – Emil Jeřábek
    Commented Nov 5, 2022 at 21:14
  • 2
    $\begingroup$ 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. $\endgroup$
    – Anthony Quas
    Commented Nov 6, 2022 at 1:13

0

Reset to default

You must log in to answer this question.