Holes and islands in random point sets
Copyright policy )Holes and islands in random point sets
AbstractFor , let S be a set of points in in general position. A set I of k points from S is a k‐island in S if the convex hull of I satisfies . A k‐island in S in convex position is a k‐hole in S. For and a convex body of volume 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‐holes in S is in . Our estimate improves and generalizes all previous bounds. In particular, we estimate the expected number of empty simplices in S by . This is tight in the plane up to a lower‐order term. Our method gives an asymptotically tight upper bound even in the much more general setting, where we estimate the expected number of k‐islands in S.
- Charles University Czech Republic
- ETH Zurich Switzerland
- Leibniz Association Germany
- Institut für Mathematik Germany
- TECHNISCHE UNIVERSITAT BERLIN Germany
Computational Geometry (cs.CG), FOS: Computer and information sciences, Erdős-Szekeres type problem, Discrete Mathematics (cs.DM), empty polytope, stochastic geometry, G.3, Convex position, Stochastic geometry; Random point set; Erdős-Szekeres type problem; k-hole; k-island; Empty polytope; Convex position; Horton set, G.2.1, 510, G.2.1; I.3.5; G.3, FOS: Mathematics, Mathematics - Combinatorics, random point set, Stochastic geometry, Empty polytope, Random convex sets and integral geometry (aspects of convex geometry), Horton set, I.3.5, Probability (math.PR), 004, convex position, k-hole, Random point set, Computer Science - Computational Geometry, Geometric probability and stochastic geometry, Combinatorics (math.CO), k-island, Mathematics - Probability, Computer Science - Discrete Mathematics, ddc: ddc:004
Computational Geometry (cs.CG), FOS: Computer and information sciences, Erdős-Szekeres type problem, Discrete Mathematics (cs.DM), empty polytope, stochastic geometry, G.3, Convex position, Stochastic geometry; Random point set; Erdős-Szekeres type problem; k-hole; k-island; Empty polytope; Convex position; Horton set, G.2.1, 510, G.2.1; I.3.5; G.3, FOS: Mathematics, Mathematics - Combinatorics, random point set, Stochastic geometry, Empty polytope, Random convex sets and integral geometry (aspects of convex geometry), Horton set, I.3.5, Probability (math.PR), 004, convex position, k-hole, Random point set, Computer Science - Computational Geometry, Geometric probability and stochastic geometry, Combinatorics (math.CO), k-island, Mathematics - Probability, Computer Science - Discrete Mathematics, ddc: ddc:004
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).5 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!