I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane (the Happy-Ending Problem), and I know that there are higher-dimensional extensions. A great source (albeit a decade out of date) is:

  • Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey", Bulletin of the American Mathematical Society 37 (04): 437–458, AMS link.

My query concerns the probability that $n$ random 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:

  • József Balogh, Hernán González-Aguilar, Gelasio Salazar, "Large convex holes in random point sets" (arXiv link).

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!


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.

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.

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.

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.

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.

  • $\begingroup$ @Douglas: Thanks for the clear answer! $\endgroup$ – Joseph O'Rourke Sep 23 '12 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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