Premium
Holes and islands in random point sets
Author(s) -
Balko Martin,
Scheucher Manfred,
Valtr Pavel
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21037
Subject(s) - combinatorics , convex hull , mathematics , general position , convex body , position (finance) , regular polygon , upper and lower bounds , plane (geometry) , convex set , set (abstract data type) , point (geometry) , order (exchange) , term (time) , hull , geometry , mathematical analysis , physics , convex optimization , computer science , finance , economics , programming language , quantum mechanics , marine engineering , engineering
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 .