License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12172/
Go to the corresponding LIPIcs Volume Portal

Balko, Martin ; Scheucher, Manfred ; Valtr, Pavel

Holes and Islands in Random Point Sets

pdf-format:
LIPIcs-SoCG-2020-14.pdf (0.7 MB)

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
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI