文章基本信息

标题：Holes and Islands in Random Point Sets
本地全文：下载
作者：Martin Balko ; Manfred Scheucher ; Pavel Valtr 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：164
页码：14:1-14:16
DOI：10.4230/LIPIcs.SoCG.2020.14
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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].
关键词：stochastic geometry; random point set; ErdÅ's-Szekeres type problem; k-hole; k-island; empty polytope; convex position; Horton set