Large area convex holes in random point sets (Q2821621)

Let \(K\) be a convex set in the plane and let \(K_n\) be a set of \(n\) points chosen independently and uniformly at random from \(K\). A \(K_n\)-hole (or simply a hole) is a subset of \(K\) whose interior does not contain any point of \(K_n\). In [\textit{J. Balogh} et al., Comput. Geom. 46, No. 6, 725--733 (2013; Zbl 1271.52003)] has been proved that with high probability the size of the largest (in the number of vertices) polygonal hole with vertices in \(K_n\) is \(\Theta({{\log n}\over{\log\log n}})\). The present work considers the largest hole in terms of area rather than in terms of the number of vertices. The main results of the paper are the following statements.NEWLINENEWLINE\textbf{Theorem 1.} Let \(K\), \(L\) be planar convex sets. Suppose for normalization purposes that the area of \(K\) is 1. Let \(K_n\) be a set of \(n\) points chosen independently and uniformly at random from \(K\). Let \(\mathrm{MAX}_L(K_n)\) denote the random variable that measures the largest (in terms of area) hole that is homothetic to \(L\). Then with high probability \(\mathrm{MAX}_L(K_n) = (1+ o(1)){{\log n}\over {n}}\).NEWLINENEWLINE\textbf{Theorem 2.} Let \(K\) be a convex set in the plane with area 1. Let \(K_n\) be a set of \(n\) points chosen independently and uniformly at random from \(K\). Let \(\mathrm{MAX}(K_n)\) denote the random variable that measures the largest (in terms of area) convex hole. Then with high probability \((1+o(1)){{\log n}\over{n}}\leq\mathrm{MAX}(K_n)\leq (4+o(1)){{\log n}\over{n}}\).NEWLINENEWLINENote that while the lower bound in Theorem 2 is an immediate consequence of the lower bound in Theorem 1, the upper bound in Theorem 2 cannot be derived from the upper bound in Theorem 1, because the set \(L\) is fixed in advance, whereas Theorem 2 is a statement over all convex regions.NEWLINENEWLINELet \(\mathrm{POLYMAX}(K_n)\) be the random variable that measures the largest (in terms of area) convex polygon with vertices in \(K_n\). Then \(\mathrm{POLYMAX}(K_n)\) has the same upper and lower limits as \(\mathrm{MAX}(K_n)\). For a related work see [\textit{C. Hervías} et al., ``On finding large polygonal voids using Delaunay triangulation: the case of planar point sets'', in: Proceedings of the 22nd international meshing roundtable. New York: Springer. 275--292 (2014)].