Minimal polytope enclosing a sphere

Question

Given a unit ball in d dimensions (euclidean distance) and an allotment of points $n > d$, can we choose the set of n points such that their convex hull contains the ball and the volume of the convex hull is low? (the exact optimum would be best, but any approximation or any objective that admits gradient descent would be very helpful)

In the two-dimensional case, we would always want to use the smallest regular polygon over n points. However, I can’t even properly reason about the 3-dimensional case (let alone d-dimensional).

This popped up in some research idea I had. The problem statement involves verifying a specific property $\forall x \in S$ for different sets that are usually $\ell_p$ balls. There is this cool algorithm that works for simplices/polytopes. I was curious if it could be extended to $\ell_2$ balls by getting a conservative bounding polytope and verifying the harder problem.

Answer 1

Some general comments:

The regular polytopes are probably best for their combinations of $n$ and $d$. Note that once $d \ge 5$ only 3 polytopes exist, the equivalents of the tetrahedra, the octahedra and the cube. For the latter two it is fairly straightforward to compute the exact coordinates and volumes of the polytopes.

If $n$ is much bigger than $d$ one can get a bound by putting all the points on a sphere with somewhat bigger radius than 1 and then argueing that the points form a sufficiently dense net so that their convex hull contains the unit ball. The volume of the outer sphere would give an upper bound for the volume of the convex hull.

Finding exact solutions is probably hard and has to be done individually numerically. I don't think the solutions for small $n$ will form any regular pattern.

Answer 2

For large $n$ on a sphere, points might be in more or less of a hexagonal pattern. If each point has a hexagon of area $4\pi/n$, the distance between points would be $O(1/\sqrt n)$.
Take three neighbouring vertices that form a small triangle. Suppose the triangle's centroid lies on the unit sphere. A right-angled triangle with the sphere's centre, the centroid and a vertex means the points are at a radius $1+O(1/n)$ from the sphere's centre.
So the volume of the polyhedron is $4\pi/3(1+O(1/n))$.
For general $d$, each vertex has its neighbouring $(d-1)$-volume $O(n^{-1})$. The distance between vertices is $O(n^{-1/(d-1)})$. The radius of vertices is then $1+O(n^{-2/(d-1)})$. The relative $d$-volume of the polytope to the $d$-sphere is $1+O(n^{-2/(d-1)})$.