Average size of extreme points of convex hull of $N$ points

Question

Fix $n$ a (small) integer.

Let $N$ be a (big) integer. Consider $N$ random points in the $n$-dimensional unit cube $[0, 1]^n$. The $N$ points are independently uniformly distributed.

Define $V(N)$ to be the expectation of the number of extreme points of the convex hull of the $N$ points.

Question: when $N$ grows to infinity, how fast does $V$ grow?

---

For $n = 1$, one has $V = 2$;

For $n = 2$, my intuition suggests $V \simeq N^{1/2}$, but I'm not quite sure;

Similarly, for general $n$, my intuition suggests $V \simeq N^{(n - 1)/n}$.

---

Are there known results on this problem or similar problems?

Answer 1

The result turns out to be very different depending whether you draw your points from a polytope or a smooth body.

This paper (Random Points and Lattice Points in Convex Bodies, Bárány in Bull. AMS 2008) contains the result you desire, and many pointers to the (very abundant) literature no this topic.

Turns out your intuition is far from the right answer, which as pointed out by Joseph O'Rourke is $$ V \simeq (\log N)^{n-1}$$ for points drawn in a polytope, but it is quite closer to the answer for points drawn from a smooth convex body: $$ V \simeq N^{\frac{n-1}{n+1}} $$ (see Section 9 of the above paper for both results).

The current research is more focused about higher-order results (CLT etc.), but the Poissonian case (where the number $N$ is chosen randomly in precisely the way that gives independence to the events "there is a point in $A$" and "there is a point in $B$" whenever $A$ and $B$ are disjoint) is much better understood, as far as I know.

Answer 2

Grows as $O(\log^{n−1} N)$. Below, your $n$ is H-P's $d$, and your $N$ is H-P's $n$. So: $O(\log^{d−1} n)$, or, to avoid notational ambiguity: $O((\log n)^{d-1})$

Har-Peled, Sariel. "On the expected complexity of random convex hulls." arXiv:1111.5340 (2011).

"We prove that the expected number of points that lie on the boundary of the quadrant hull of $n$ points, chosen uniformly and independently from the axis-parallel unit hypercube in $\mathbb{R}^d$, is $O(\log^{d−1} n)$. This readily imply[sic] $O(\log^{d−1} n)$ bound on the expected number of maxima and the expected number of vertices of the convex hull of such a point set. Those bounds are known [BKST78], but we believe the new proof is simpler and more intuitive."

Here is the [BKST78] reference: J. L. Bentley, H. T. Kung, M. Schkolnick, and C. D. Thompson. On the average number of maxima in a set of vectors and applications. Journal of the ACM, 25:536–543, 1978.