Empty convex polytopes for random point sets - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T22:06:38Z http://mathoverflow.net/feeds/question/107875 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/107875/empty-convex-polytopes-for-random-point-sets Empty convex polytopes for random point sets Joseph O'Rourke 2012-09-23T02:01:34Z 2012-09-23T06:22:27Z <p>I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane (the <a href="http://en.wikipedia.org/wiki/Happy_Ending_problem" rel="nofollow">Happy-Ending Problem</a>), and I know that there are higher-dimensional extensions. A great source (albeit a decade out of date) is:</p> <ul> <li>Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey", <em>Bulletin of the American Mathematical Society</em> 37 (04): 437–458, <a href="http://www.ams.org/journals/bull/2000-37-04/S0273-0979-00-00877-6/home.html" rel="nofollow">AMS link</a>.</li> </ul> <p>My query concerns the probability that $n$ <em>random</em> points in $\mathbb{R}^d$ contain an empty $k$-vertex convex polytope. This summer a result was obtained for a planar version of this question:</p> <ul> <li>József Balogh, Hernán González-Aguilar, Gelasio Salazar, "Large convex holes in random point sets" (<a href="http://arxiv.org/abs/1206.0805" rel="nofollow">arXiv link</a>).</li> </ul> <p>In particular, I wonder if there is a result that there is an empty convex polytope with "approximately" $\Omega(\log n)$ vertices? ("approximately": Perhaps mitigated by $\log \log n$ factors, etc.) If not, what is the best lowerbound that can be claimed? This is primarily a reference request. Thanks!</p> http://mathoverflow.net/questions/107875/empty-convex-polytopes-for-random-point-sets/107885#107885 Answer by Douglas Zare for Empty convex polytopes for random point sets Douglas Zare 2012-09-23T06:22:27Z 2012-09-23T06:22:27Z <p>Yes, the $2$-dimensional lower bound $\Omega( \frac{\log n}{\log\log n})$ implies a lower bound of that form in all higher dimensions by projecting to a plane. </p> <p>If a set of points is not in convex position, then some convex combination of them equals another point in the set, and this is true for their projections. So, any hole in the projection pulls back to a hole. </p> <p>The projected points are not always uniformly distributed. However, they are for a product region such as a rectangular solid, so the expected largest hole is at least $\Omega( \frac{\log n}{\log\log n})$ for a rectangular solid. </p> <p>For any two bounded convex $d$-dimensional regions $R$ and $S$, $E(\text{HOL}(R_n)) = \Theta(E(\text{HOL}(S_n)))$ using the notation of theorem $1$ in the Balogh, González-Aguilar, and Salazar paper. In fact, although they state this for convex regions in the plane, they never mention or use that the regions are $2$-dimensional in the proof. </p> <p>Therefore by the easier side of Balogh, González-Aguilar, and Salazar's result, in dimension at least $2$, the expected largest convex hole in a random set of $n$ points in any bounded convex region is $\Omega(\frac{\log n}{\log\log n} )$. I don't know whether their harder upper bound of the same form also extends to higher dimensions, but I suspect that it does.</p>