We know $n>2$ and worst case its a triangle, best case the points all lie on a circle. Can we generalize to higher dimensions? What's the probability that the size of the convex hull of $n$ points randomly selected in a circle is $k$?
3
$\begingroup$
$\endgroup$
5
$\begingroup$
$\endgroup$
The expected number of vertices of the convex hull of $n$ points, chosen uniformly and independently from a disk, is $O(n^{\frac{1}{3}})$.
The result goes back to the 1960's. A nice proof is in Har-Peled, "On the expected complexity of random convex hulls" (1997), from which the above sentence is quoted. (arXiv version abstract.)
answered Mar 30 '13 at 12:04
