Holes and islands in random point sets
Martin Balko, Manfred Scheucher, Pável Valtr · Random Structures and Algorithms · 2021
Abstract For , let S be a set of points in in general position. A set I of k points from S is a k‐island in S if the convex hull of I satisfies . A k‐island in S in convex position is a k‐hole in S. For and a convex body 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 . Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in S by . This is tight in the plane up to a lower‐order term. Our method gives an asymptotically tight upper bound even in the much more general setting, where we estimate the expected number of k‐islands in S.