Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 19 down vote accepted

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.

share|improve this answer
2  
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
2  
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
1  
@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
    
For $n=6$, I think you mean $199/720$...? –  Joseph O'Rourke Apr 5 '12 at 17:21
    
@Joseph O'Rourke: yes, thanks, fixed. –  quid Apr 5 '12 at 17:26

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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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