Average Area of a Random Hull

Yesterday, someone on MathOverflow asked

Consider nn points generated randomly and uniformly on a unit square. What is the expected value of the area (as a function of nn) enclosed by the convex hull of the set of points?

Someone quickly cited 2004 paper provides an analytical result for the cases where n=3n=3 and n=4n=4:

For n=3n=3 the expected value is 11/14411/144 and for n=4n=4 it is 11/7211/72.

This is certainly a nontrivial result. However, the value can be approximated by generating a large number of random points, finding the area of the convex hull, and averaging the areas. Of course, finding the convex hull and the area of the convex hull of a set of points requires a little work. Mathematica provides functions for generating random points and finding the area of the convex hull of a set of points quickly. As a result, I was able to perform a Monte Carlo simulation for the n=3n=3 and n=4n=4 case in a couple of lines of Mathematica code:

Sampling 5000 cases for each returned results fairly close to the predicted average.

Last updated on Feb 05, 2024 20:00 -0500
Feedback