Area Enclosed by the Convex Hull of a Set of Random Points - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T04:32:12Z http://mathoverflow.net/feeds/question/93099 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/93099/area-enclosed-by-the-convex-hull-of-a-set-of-random-points Area Enclosed by the Convex Hull of a Set of Random Points unknown (google) 2012-04-04T12:00:26Z 2012-04-05T17:29:35Z <p>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?</p> http://mathoverflow.net/questions/93099/area-enclosed-by-the-convex-hull-of-a-set-of-random-points/93104#93104 Answer by Joseph O'Rourke for Area Enclosed by the Convex Hull of a Set of Random Points Joseph O'Rourke 2012-04-04T12:25:22Z 2012-04-05T17:29:35Z <p>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., <a href="http://mathworld.wolfram.com/SquarePointPicking.html" rel="nofollow">this MathWorld article</a>.</p> <p>[<em>Updated with comparisons between the above formula</em> (Asymp) <em>and the exact formula</em> (Exact) <em>found by</em> <b>quid</b>.] <code>$$\begin{array}{lcccc} n &amp; &amp; \mathrm{Asymp} &amp; &amp;\mathrm{Exact} \\ n=10 &amp; : &amp; A = 0.39 &amp; : &amp; 0.44 \\ n=100 &amp; : &amp; A = 0.89 &amp; : &amp; 0.88 \\ n=1000 &amp; : &amp; A = 0.98 &amp; : &amp; 0.98 \end{array}$$</code></p> http://mathoverflow.net/questions/93099/area-enclosed-by-the-convex-hull-of-a-set-of-random-points/93109#93109 Answer by quid for Area Enclosed by the Convex Hull of a Set of Random Points quid 2012-04-04T12:50:35Z 2012-04-05T17:27:30Z <p><strong>Update:</strong> 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 <code>$$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)$$</code> yielding (starting with $n=3$): $11/144$, $11/72$, $79/360$, $199/720$, and so on.</p> <p>The paper contains in fact a more general result, where the problem is solved for any convex $m$-gon; not just the square. </p> <p>For asymtotics see other answer(s).</p> <p>--</p> <p>Old version (highly incomplete and wrong guess)</p> <p>For $n=3$ the expected value is $11/144$ and for $n=4$ it is $11/72$. </p> <p>This information is taken from a <a href="http://www.math.kth.se/~johanph/area12.pdf" rel="nofollow">somewhat recent paper (2004) by Johan Philip</a> 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. </p> http://mathoverflow.net/questions/93099/area-enclosed-by-the-convex-hull-of-a-set-of-random-points/93110#93110 Answer by Raphael L for Area Enclosed by the Convex Hull of a Set of Random Points Raphael L 2012-04-04T12:50:46Z 2012-04-04T12:50:46Z <p>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.</p>