12
$\begingroup$

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?

$\endgroup$

3 Answers 3

21
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$
    – user9072
    Apr 4, 2012 at 13:05
  • 2
    $\begingroup$ 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? $\endgroup$ Apr 5, 2012 at 3:37
  • 1
    $\begingroup$ @Daniel Litt: thanks for the question; turns out my guess was wrong. The edit to appear soon, should clarify things. $\endgroup$
    – user9072
    Apr 5, 2012 at 16:35
  • $\begingroup$ @quid: Thanks! That does indeed clarify things :). $\endgroup$ Apr 6, 2012 at 16:53
13
$\begingroup$

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

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

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.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.