Area Enclosed by the Convex Hull of a Set of Random Points - MathOverflow

Area Enclosed by the Convex Hull of a Set of Random Points

2012-04-04T12:00:26Z

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

Answer by Joseph O'Rourke for Area Enclosed by the Convex Hull of a Set of Random Points

2012-04-04T12:25:22Z

Let $A$ be the expected area. Then: $$\lim_{n \rightarrow \infty} \frac{n}{\ln n} (1 - A) = \frac{8}{3} \;.$$ This can be found in many places, e.g., this MathWorld article.

[Updated with comparisons between the above formula (Asymp) and the exact formula (Exact) found by quid.] $$ \begin{array}{lcccc} n & & \mathrm{Asymp} & &\mathrm{Exact} \\ n=10 & : & A = 0.39 & : & 0.44 \\ n=100 & : & A = 0.89 & : & 0.88 \\ n=1000 & : & A = 0.98 & : & 0.98 \end{array} $$

Answer by quid for Area Enclosed by the Convex Hull of a Set of Random Points

2012-04-04T12:50:35Z

Update: By a result of Buchta (Zufallspolygone in konvexen Vielecken, Crelle, 1984; available on digizeitschriften.de) there is a general formula for this expected value, it is $$1 -\frac{8}{3(n+1)} \bigl( \sum_{k=1}^{n+1} \frac{1}{k} (1 - \frac{1}{2^k}) - \frac{1}{(n+1)2^{n+1}} \bigr) $$ yielding (starting with $n=3$): $11/144$, $11/72$, $79/360$, $199/720$, and so on.

The paper contains in fact a more general result, where the problem is solved for any convex $m$-gon; not just the square.

For asymtotics see other answer(s).

Old version (highly incomplete and wrong guess)

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

This information is taken from a somewhat recent paper (2004) by Johan Philip where the respective distribution functions are studied in detail. I did not see any mention of exact values for other small values of $n$ there (the asymptocic result given already is mentioned though), so they might be unknown.

Answer by Raphael L for Area Enclosed by the Convex Hull of a Set of Random Points

2012-04-04T12:50:46Z

For any convex set $K$ in dimension $d$ with volume $V(K)$, it is aymptotically $$V(K)-\frac{T(K)}{(d+1)^{d-1}(d-1)!}n^{-1}ln(n)^{d-1}+O(n^{-1}ln(n)^{d-2}ln(ln(n)))$$ (see {New perspectives in stochastic geometry} by W. Kendall and I. Molchanov, p. 49) where $T(K)$ is the number of "flags", i.e. of sequences $f_0\subset f_1 \subset ... \subset f_{d-1}$ where $f_i$ is an $i$-dimensional facet. There is an abundant literature for random convex hulls and if you're interested there might be an exact closed formula for the square.