Large convex holes in random point sets (Q1947987)

If \(P\) is a set of points in the plane, then a \textbf{convex hole} (or empty convex polygon) of \(P\) is a convex polygon with vertices in \(P\) that contains no points of \(P\) in its interior. The authors prove that, if \(R\) is a bounded convex region in the plane, then the expected number of vertices of the largest convex hole of a set of \(n\) random points chosen independently and uniformly at random over \(R\) is \(\Theta(\log n/(\log\log n ))\) and is independent of the shape of \(R\). Moreover, they prove that \(\Theta(\log n/(\log\log n ))\) is the size of the largest convex hole with probability \(1-o(1)\).