Holes and islands in random point sets. Issue 3 (12th July 2021) - Balko, Martin; Scheucher, Manfred; Valtr, Pavel
Abstract: For d ∈ ℕ, let S be a set of points in ℝ d in 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 ⊆ ℝ d of 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 by 2 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 .