3
$\begingroup$

Given any convex set $A\in\mathbb{R}^d$, we denote by $V(A)$ its $d$-volume. Furthermore, given any two convex sets $A_1,A_2\in\mathbb{R}^d$, we denote by $V_{A_1,A_2}$ the $d$-volume of the symmetric difference $V\left(A_1 \triangle A_2\right)$ (informally, a small value of $V_{A_1,A_2}$ compared to $V(A_1)$ and $V(A_2)$, can viewed as $A_1$ well approximating $A_2$ and $A_2$ well approximating $A_1$).

Let $\mathcal{S}$ be the set of all $d$-dimensional convex shapes $S$ such that there exists a constant $\delta\in (0,1]$ independent of $d$ for which we have $V(S)\ge\delta V(B)$, where $B$ is the bounding box of $S$.

Question: How can we prove or disprove that for all convex shapes $S\in\mathcal{S}$, there exists a convex polytope $P$ satisfying the following property?

  • Given any constant $\gamma>0$ independent of $d$ for which we have $V_{S,P}\le \gamma V(S)$, there exists an integer $k(\gamma)$ independent of $d$ such that the number of $(d-1)$-dimensional facets of $P$ is upper bounded by $d^{k(\gamma)}$.

Note: This post stems from a discussion with Anthony Quas in the comments of Approximating any convex shape in $\mathbb{R}^d$ with a polytope having $\mathrm{poly}(d)$ facets.

Note that for $\gamma\ge\frac{1}{\delta}-1$ the polytope $P$ can be trivially identified as bounding box $B$ of $S$.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ "Let $S_\delta$ be a convex shape with bounding box $B$, such that there exists a constant $\delta\in(0,1]$ independent of $d$ [...]": I am a bit confused about what is being said here. Do you fix a $\delta$ and then $S_\delta$ can be understood as the class of convex bodies (of any dimension) that can be "well-approximated" by some encompassing cuboid $B$? $\endgroup$
    – M. Winter
    Commented Nov 17, 2022 at 18:24
  • 1
    $\begingroup$ Thank you for your comment @M.Winter . I just mean that $S_{\delta}$ is defined as any $d$-dimensional convex body occupying a constant fraction of its bounded box in $\mathbb{R}^d$, i.e., its $d$-volume is a constant fraction of the $d$-volume of its bounded box. For instance, $d$-balls cannot be part of the class of bodies formed by $\bigcup_{\delta\in(0,1]}S_{\delta}$. Would it be better to avoid mentioning explicitly $\delta$ in the text? $\endgroup$
    – Penelope Benenati
    Commented Nov 18, 2022 at 11:08
  • 1
    $\begingroup$ So $S_\delta$ is indeed a class of bodies, not a single body, and I should read "for all convex shapes $S_\delta$" as "for all convex shapes $S\in S_\delta$"? $\endgroup$
    – M. Winter
    Commented Nov 18, 2022 at 11:10
  • 1
    $\begingroup$ I corrected the problem text based on your comment @M.Winter . Thank you! $\endgroup$
    – Penelope Benenati
    Commented Nov 18, 2022 at 11:18
  • 1
    $\begingroup$ I don't think this is true. Pick any $\delta$, e.g., $\delta=1/2$. Then consider the convex shape that is a cube, but with its corners rounded down like a ball. So it is the intersection of a cube and a ball with the same center such that it fills out exactly half of the cube. Then you will run into the same problem as you did in your linked question with the ball. $\endgroup$
    – domotorp
    Commented Nov 28, 2022 at 5:22

0

Reset to default

You must log in to answer this question.