Holes and islands in random point sets

For $d \ge 2$, let $S$ be a finite set of points in $\mathbb R ^d$ in general position. A set $H$ of $k$ points from $S$ is a $k$-hole in $S$ if all points from $H$ lie on the boundary of the convex hull conv$(H)$ of $H$ and the interior of conv$(H)$ does not contain any point from $S$. A set $I$ of $k$ points from $S$ is a $k$-island in $S$ if conv$(I)\cap S=I$. Note that each $k$-hole in $S$ is a $k$-island in $S$.

For fixed positive integers $d, k$ and a convex body $K$ in $\mathbb R^d$ with $d$-dimensional Lebesgue measure 1, let $S$ be a set of $n$ points chosen uniformly and independently at random from $K$. We show that the expected number of $k$-islands in $S$ is in $O(n^d)$. In the case $k=d+1$, we prove that the expected number of empty simplices (that is, $d+1$-holes) in $S$ is at most $2^{d-1} d! {n \choose d}$.

Our results improve and generalize previous bounds by Bárány and Füredi (1987), Valtr (1995), Fabila-Monroy and Huemer (2012), and Fabila-Monroy, Huemer, and Mitsche (2015). Joint work with Martin Balko and Manfred Scheucher.