Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.14
URN: urn:nbn:de:0030-drops-121722
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12172/
Balko, Martin ; Scheucher, Manfred ; Valtr, Pavel
Holes and Islands in Random Point Sets
| pdf-format: |
|
Abstract
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].
BibTeX - Entry
@InProceedings{balko_et_al:LIPIcs:2020:12172,
author = {Martin Balko and Manfred Scheucher and Pavel Valtr},
title = {{Holes and Islands in Random Point Sets}},
booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)},
pages = {14:1--14:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-143-6},
ISSN = {1868-8969},
year = {2020},
volume = {164},
editor = {Sergio Cabello and Danny Z. Chen},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12172},
URN = {urn:nbn:de:0030-drops-121722},
doi = {10.4230/LIPIcs.SoCG.2020.14},
annote = {Keywords: stochastic geometry, random point set, Erdős-Szekeres type problem, k-hole, k-island, empty polytope, convex position, Horton set}
}
| Keywords: | stochastic geometry, random point set, Erdős-Szekeres type problem, k-hole, k-island, empty polytope, convex position, Horton set | |
| Seminar: | 36th International Symposium on Computational Geometry (SoCG 2020) | |
| Issue date: | 2020 | |
| Date of publication: | 08.06.2020 |
