Given a $d$-ball $\mathcal{S}^{d}$, let $P\_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}\_n$ the convex hull of $P\_n$. We denote by $V(\mathcal{S}^{d})$ and $V(\mathcal{C}\_n)$ the volume of $\mathcal{S}^d$ and $\mathcal{C}\_n$ respectively.




---


**Question:** Can we prove that, for all constant values $a\in (0,1)$, $n$ has to grow superpolynomially in $d$ (for $d\to\infty$) to satisfy $\mathbb{E}[V(\mathcal{C}\_n)]\ge aV(\mathcal{S}^{d})$ ?




---




---


***Note:*** *Do you please have any reference for the convex hull $\mathcal{C}\_n^\*$ of the $n$ points of $\mathcal{S}^{d-1}$ maximizing $V(\mathcal{C}\_n)$ (so that we can hopefully avoid to calculate the expectation $\mathbb{E}[V(\mathcal{C}\_n)]$ if $n=\omega(\mathrm{poly}(d))$ to satisfy $V(\mathcal{C}\_n^\*)\ge aV(\mathcal{S}^{d})$ for any $a\in(0,1)$ when $d\to\infty$) ?*



$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
It's true deterministically in $P\_n$. In fact, here's a proof that there is some $c$ so that if $n \leq e^{cd}$ then we have that $V(C\_n)/V(S^d) \to 0$.


We'll work with the ball of radius $1$. For a given configuration $P\_n$, let $p$ denote the probability that a point chosen uniformly from the sphere lies in the $C\_n$; then $p = V(C\_n)/V(S^d)$. Let $X$ be a point chosen uniformly at random form the ball $S^d$.


If $X \in C\_n$, then there must be a point $y \in P\_n$ so that $\langle y , \frac{X}{\|X\|} \rangle \geq \|X\|$; otherwise, then hyperplane with normal vector $X/\|X\|$ separates $X$ from the set $P\_n$. Union bounding over all points we have $$ \mathbb{P}(X \in C\_n) \leq \sum\_{y \in P\_n} \mathbb{P}\left( \left\langle y, \frac{X}{\|X\|} \right\rangle \geq \| X \|\right) = n \mathbb{P}\left( \left\langle Y, \frac{X}{\|X\|} \right\rangle \geq \| X \|\right)$$ where in the last line we used spherically symmetry of $X$, and we let $Y$ be chosen uniformly at random from the sphere.


It is thus sufficient to show that this probability decays exponentially. Note that $\mathbb{P}(\|X \| < 1/2) = 2^{-d}$ and so $$\mathbb{P}\left( \left\langle Y, \frac{X}{\|X\|} \right\rangle \geq \| X \|\right) < 2^{-d} + \mathbb{P}\left( \left\langle Y, \frac{X}{\|X\|} \right\rangle \geq 1/2\right).$$ By rotational symmetry of $Y$, we may assume WLOG that $X/\|X\|$ is the first coordinate vector $e\_1$. We may sample $Y$ by considering $d$ i.i.d. standard Gaussians $Z = (Z\_1,\ldots,Z\_d)$ and taking $Y = Z/\|Z\|$. Thus we have that $\langle Y, e\_1 \rangle$ has the same distribution as $\frac{Z\_1}{\|Z\|}$. We have that $\mathbb{P}(\|Z\| < \sqrt{d}/2) \leq e^{-cd}$, and so $$ \mathbb{P}\left(\frac{Z\_1}{\|Z\|} \geq 1/2\right) \leq e^{-cd} + \mathbb{P}(Z\_1 \geq \sqrt{d}/4) \leq e^{-c'd}.$$


