2026-07-24T11:55:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12172 2024-03-06T10:49:37Z ddc:004 open_access

Holes and Islands in Random Point Sets Balko, Martin Scheucher, Manfred Valtr, Pavel stochastic geometry random point set Erdős-Szekeres type problem k-hole k-island empty polytope convex position Horton set For d ∈ ℕ, let S be a finite set of points in ℝ^d in general position. A set H of k points from S is a k-hole in S if all points from H lie on the boundary of the convex hull conv(H) of H and the interior of conv(H) does not contain any point from S. A set I of k points from S is a k-island in S if conv(I) ∩ S = I. Note that each k-hole in S is a k-island in S. For fixed positive integers d, k and a convex body K in ℝ^d with d-dimensional Lebesgue measure 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-islands in S is in O(n^d). In the case k=d+1, we prove that the expected number of empty simplices (that is, (d+1)-holes) in S is at most 2^(d-1) ⋅ d! ⋅ binom(n,d). Our results improve and generalize previous bounds by Bárány and Füredi [I. Bárány and Z. Füredi, 1987], Valtr [P. Valtr, 1995], Fabila-Monroy and Huemer [Fabila-Monroy and Huemer, 2012], and Fabila-Monroy, Huemer, and Mitsche [Fabila-Monroy et al., 2015]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Balko and Manfred Scheucher and Pavel Valtr 2020 Is Part Of LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2020.14 urn:nbn:de:0030-drops-121722 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.14 eng https://creativecommons.org/licenses/by/3.0/legalcode