# What is the expected size of the convex hull of $n$-points selected randomly in a $2d$-circle?

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$?

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.)

Amazing result! Some code for the computation-minded.

import numpy as np
from scipy.spatial import ConvexHull

def countVertex(n):
points = np.random.random((n, 2))
hull = ConvexHull(points)
return hull.nsimplex

def testN(n, nTrial=20):
return np.array( [ countVertex(n) for i in range(nTrial) ])

def testAllN(n_list):
nTrial = 20
nN = len(n_list)
result = np.zeros((nN, nTrial))
for i,n in enumerate(n_list):
result[i,:] = testN(n, nTrial)
np.savetxt('result.dat', result)

testAllN(range(5,100,5))


A sample result is below. The fitting line is $$2.92 x^{0.318}$$.

• The code samples random points from a unit square instead of a unit disk, but the 1/3 scaling seems to apply as well. Commented Oct 14, 2021 at 19:07