Large Area Convex Holes in Random Point Sets
Octavio Arizmendi, Gelasio Salazar · SIAM Journal on Discrete Mathematics · 2016
Let $K, L$ be convex sets in the plane. For normalization purposes, suppose that the area of $K$ is 1. Suppose that a set $K_n$ of $n$ points is chosen independently and uniformly over $K$, and call a subset of $K$ a hole if it does not contain any point in $K_n$. It is shown that with high probability the largest area of a hole homothetic to $L$ is $(1+o(1)) \log{n}/n$. We also consider the problems of estimating the largest area convex hole and the largest area of a convex polygonal hole; with vertices in $K_n$. For these two problems we give an answer that is asymptotically tight within a factor of 4.