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

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?

-

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.

--

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.

-
Some additional information not directly related: the analog result for 4 points in a cube is rather recent (Zinani; 2003) where the solution is 3977/216000 - pi^2 / 2160 . So, I really guess explicit values for most n could well be unknown. – quid Apr 4 '12 at 13:05
Do you know if in the $2$-dimensional case the expected values continue to be rational? If so, is there any easy way to see it? – Daniel Litt Apr 5 '12 at 3:37
@Daniel Litt: thanks for the question; turns out my guess was wrong. The edit to appear soon, should clarify things. – quid Apr 5 '12 at 16:35
@quid: Thanks! That does indeed clarify things :). – Daniel Litt Apr 6 '12 at 16:53

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.

-

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

-
Thanks, it's a start. Can we say anything about relatively small values of $n$ (i.e. not in the limit behavior)? – user18011 Apr 4 '12 at 12:33