Holes and islands in random point sets

For d ∈ ℕ , let S be a set of points inℝ din general position. A set I of k points from S is a k ‐ island in S if the convex hull conv ( I ) of I satisfies conv ( I ) ∩ S = I . A k ‐island in S in convex position is a k ‐ hole in  S . For d , k ∈ ℕ and a convex body K ⊆ ℝ dof volume 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 ‐holes in S is in O ( n d ) . Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in S by2 d − 1 · d ! ·n d. This is tight in the plane up to a lower‐order term. Our method gives an asymptotically tight upper bound O ( n d ) even in the much more general setting, where we estimate the expected number of k ‐islands in S .