Holes and islands in random point sets. Issue 3 (12th July 2021)

• Record Type: Journal Article
• Authors: Balko, Martin; Scheucher, Manfred; Valtr, Pavel
• Is Part Of: Random structures & algorithms. Volume 60:Issue 3(2022)
• Page Start: 308
• Page End: 326
• Publication Date: 2021-07-12
• Subjects: convex position -- k‐hole -- k‐island -- random point set -- stochastic geometry; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21037
• Languages: English
• ISSNs: 1042-9832

Abstract

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 .