Holes and islands in random point sets

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10420193" target="_blank" >RIV/00216208:11320/20:10420193 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.4230/LIPIcs.SoCG.2020.14" target="_blank" >https://doi.org/10.4230/LIPIcs.SoCG.2020.14</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.SoCG.2020.14" target="_blank" >10.4230/LIPIcs.SoCG.2020.14</a>

Result language
angličtina
Original language name
Holes and islands in random point sets
Original language description
For dELEMENT OFN, let S be a finite set of points in Rd in general position. A set H of k points from S is a emph{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 emph{k-island} in S if conv(I)INTERSECTIONS=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~Rd 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(nd). 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 2d-1DOT OPERATOR d!DOT OPERATOR (nd). Our results improve and generalize previous bounds by Bárány and Füredi (1987), Valtr (1995), Fabila-Monroy and Huemer (2012), and Fabila-Monroy, Huemer, and Mitsche (2015).
Czech name
—
Czech description
—

Project
<a href="/en/project/GA18-19158S" target="_blank" >GA18-19158S: Algorithmic, structural and complexity aspects of geometric and other configurations</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
36th International Symposium on Computational Geometry (SoCG 2020)
ISBN
978-3-95977-143-6
ISSN
1868-8969
e-ISSN
—
Number of pages
16
Pages from-to
1-16
Publisher name
Dagstuhl Publishing, Germany
Place of publication
Dagstuhl, Germany
Event location
Švýcarsko
Event date
Jun 23, 2020
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)