5
$\begingroup$

To my great surprise, I was unable to find any general reference on the volume of (symmetric) polytopes inscribed in, say, the unit sphere.

Let $P = absconv(v_1,\dots,v_k) $ where the $v_i$'s are unit vectors. Then, I would like to have an upper bound on the quantity :

$$\frac{vol(P)}{vol(B^2)} $$ where $B^2$ is the euclidean unit ball. Intuitively the maximal volume polytope with k vertices should be made of vertices $v_i$'s forming an $\epsilon$-net of the sphere for some $\epsilon$ (that is being "uniformly" distributed) but that's beyond the point.

In particular, I'm expecting that if $k$ is sub-exponential in $n$ then this volume ratio should go to zero. That is if $k_n = o(e^{cn})$ for every $c>0$ and $P_n$ is a polytope with $k_n$ vertices on the unit sphere of $R^n$, then $$vol(P_n) = o(vol(B^2_n))$$

Is this true ? Is there any quantitative statement about it ?

$\endgroup$
4
  • 1
    $\begingroup$ There is a ton of literature on random polytopes, for example check out "Random Polytopes, Convex Bodies, and Approximation" by I. Barany $\endgroup$ Commented Dec 30, 2021 at 4:30
  • $\begingroup$ One way to proceed would be to use measure of concentration on a ball. If the distance from each facet to the origin is bounded away from zero then you get that the small slice of the ball cut of by the facet has exponentially small volume. Then bound over all facets greedily. $\endgroup$ Commented Jan 3, 2022 at 16:59
  • $\begingroup$ Another approach would be to somehow show (if true) that the cube has the largest possible volume for any inscribed polytope with $2^n$ vertices. Since the volume of the cube already tends to zero (in relation to the volume of the ball), this would show that we do not need sub-exponential, but only sub-$2^n$. $\endgroup$ Commented Jan 3, 2022 at 23:03
  • $\begingroup$ I have the feeling you not only don't need sub-exponential, but that already $k_n=\exp(\mathcal O(n))$ could be sufficient, or is there an easy counterexample? $\endgroup$ Commented Feb 25, 2022 at 22:21

1 Answer 1

Reset to default
1
$\begingroup$

The following is a direct consequence of Theorem 1 in

If $k_n\in o(2^n)$ then $\mathrm{vol}(P_n)/\mathrm{vol}(B_n^2)\to 0$.

I recommend to take a look at the proof, it is short ($\sim$ 10 lines) and very elegant.

Likely one can say much more, but I have no appropriate source at hand: I suspect that you need super-exponentially many vertices to have a positive volume relative to the sphere. This is true for randomly chosen vertices.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.