We are given a convex shape $S$ lying inside the hypercube $[0,1]^d$ in the $d$-dimensional Euclidean space. Let the volume $V(S)$ of $S$ be $\tfrac12$ (*I guess nothing changes for any other fixed constant in $(0,1)$*).




---


**Question:** How can we prove or disprove that, for all $S$ and all $d\in\mathbb{N}$, there exists a set of points lying on its boundary such that their convex hull $C$ satisfy simultaneously the following properties?


* Its volume $V(C)$ is lower bounded by a constant independent of $d$.
* Its number of facets $\phi\_C$ grows at most polynomially in $d$.




---




---


***Note:*** *This problem is similar to [Approximation of a convex shape in the $d$-dimensional Euclidean space for $d\gg 1$](https://mathoverflow.net/q/429558/115803), but instead of bounding the number of vertices of the approximating convex polytope lying inside the given shape, we focus on bounding the number of its facets (the motivations are given below, at the end of the following paragraph).*


*The main intuition underlying this conjecture is the idea that (***very***) informally, for $d\gg 1$ if there are areas where the boundary of $S$ is far from being linear (e.g., portions of $(d-1)$-balls), the volume of the regions of $S$ bounded by such areas is disregardable compared to the volume of $S$. More generally, the same holds for areas formed by $\omega(\mathrm{poly}(d))$-many linear regions that can be viewed as good approximations of manifolds with significant curvature (in this context, such linear regions can be viewed as facets of an approximating polytope, which is conceptually linked to bounding $\phi\_C$ in this problem).*



Bounding the number of facets of a polytope to approximate a given convex shape in higher dimensions
I think ***if we assume the facets are simplexes***, the number of facets of such a polytope must grow more than exponentially, even in the easiest case where $S=[0,1]^d$. Fix a constant $\epsilon>0$.
Choose a finite subset of $\partial( [0,1]^d)$, spanning a polytope $C$ with $\phi\_C$ facets, and volume $V(C)\ge\epsilon$. We can partition $C$ into $\phi\_C$ simplexes $\{\Delta\_i\}\_{1\le i\le \phi\_C }$ with vertices in the center of $S$, so the volume of $C$ is not larger than $f$ times the largest volume of such simplexes. Parenthesis: the largest volume simplex included in a cube, say $[-1,+1]^d$, and with a vertex in the center $O$ of the cube, has wlog all its other vertices among the vertices of the cube: for we can move any vertex $v\neq O$ in the half-space whose boundary is the hyperplane for $v$, parallel to the facet of the simplex opposite to $v$, and disjoint to it, till we reach an extremal point of the cube (a vertex of the cube), and this does not decrease the volume. Thus the maximum volume among all simplexes included in $[-1,+1]^d$ with a vertex in the origin is reached by those with $d$ vertices in $\{-1,1\}^d$ plus $0$, and it is $1/d!$ times the maximum determinant of a $\{1,-1\}$ matrix of oder $d$: this is the [Hadamard's matrix problem](https://en.wikipedia.org/wiki/Hadamard%27s_maximal_determinant_problem#Hadamard%27s_bound_(for_all_n)), and the corresponding Hadamard determinant bound is $d^{d/2}$. Going back to the $\Delta\_i$ and to $[0,1]^d$, and normalizing over $V([-1,+1]^d=2^d$, we conclude that $V(\Delta\_i)\le {d^{d/2}}/({2^dd!})$ for all $i$, so $V(C)\le \phi\_C {d^{d/2}}/({2^dd!})$ so by Stirling formula $\phi\_C\ge \frac{2^dd!}{\epsilon d^{d/2}}\sim \sqrt{2\pi d}(4de^{-2})^{d/2} \epsilon^{-1}$ that grows more than exponentially.


