Tight Bounds on the Expected Number of Holes in Random Point Sets
Copyright policy )Tight Bounds on the Expected Number of Holes in Random Point Sets
AbstractFor integers and , a ‐hole in a set of points in general position in is a ‐tuple of points from in convex position such that the interior of their convex hull does not contain any point from . For a convex body of unit ‐dimensional volume, we study the expected number of ‐holes in a set of points drawn uniformly and independently at random from . We prove an asymptotically tight lower bound on by showing that, for all fixed integers and , the number is at least . For some small holes, we even determine the leading constant exactly. We improve the currently best‐known lower bound on by Reitzner and Temesvari (2019). In the plane, we show that the constant is independent of for every fixed and we compute it exactly for , improving earlier estimates by Fabila‐Monroy, Huemer, and Mitsche and by the authors.
- Charles University Czech Republic
- Technical University of Berlin Germany
- University of Hagen Germany
- Technical University of Berlin Germany
- Rolf C. Hagen Group Canada
Computational Geometry (cs.CG), FOS: Computer and information sciences, Random convex sets and integral geometry (aspects of convex geometry), Discrete Mathematics (cs.DM), \(k\)-hole, I.3.5, stochastic geometry, Probability (math.PR), G.3, G.2.1, convex position, G.2.1; I.3.5; G.3, FOS: Mathematics, Mathematics - Combinatorics, Computer Science - Computational Geometry, random point set, Geometric probability and stochastic geometry, Combinatorics (math.CO), Mathematics - Probability, Computer Science - Discrete Mathematics
Computational Geometry (cs.CG), FOS: Computer and information sciences, Random convex sets and integral geometry (aspects of convex geometry), Discrete Mathematics (cs.DM), \(k\)-hole, I.3.5, stochastic geometry, Probability (math.PR), G.3, G.2.1, convex position, G.2.1; I.3.5; G.3, FOS: Mathematics, Mathematics - Combinatorics, Computer Science - Computational Geometry, random point set, Geometric probability and stochastic geometry, Combinatorics (math.CO), Mathematics - Probability, Computer Science - Discrete Mathematics
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).4 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!