Tight Bounds on the Expected Number of Holes in Random Point Sets
| العنوان: | Tight Bounds on the Expected Number of Holes in Random Point Sets |
|---|---|
| المؤلفون: | Manfred Scheucher, Martin Balko, Pavel Valtr |
| المصدر: | Trends in Mathematics ISBN: 9783030838225 Random Structures and Algorithms Trends in Mathematics Trends in Mathematics-Extended Abstracts EuroComb 2021 Extended Abstracts EuroComb 2021-European Conference on Combinatorics, Graph Theory and Applications |
| بيانات النشر: | Springer International Publishing, 2021. |
| سنة النشر: | 2021 |
| مصطلحات موضوعية: | Computational Geometry (cs.CG), FOS: Computer and information sciences, Convex hull, Discrete Mathematics (cs.DM), General Mathematics, G.3, G.2.1, Convex position, Expected value, 01 natural sciences, Combinatorics, Set (abstract data type), 010104 statistics & probability, I.3.5, FOS: Mathematics, Mathematics - Combinatorics, Point (geometry), 0101 mathematics, Mathematics, Applied Mathematics, Probability (math.PR), 010102 general mathematics, Computer Graphics and Computer-Aided Design, Computer Science - Computational Geometry, Convex body, Combinatorics (math.CO), Stochastic geometry, General position, Software, Mathematics - Probability, Computer Science - Discrete Mathematics |
| الوصف: | For integers $d \geq 2$ and $k \geq d+1$, a $k$-hole in a set $S$ of points in general position in $\mathbb{R}^d$ is a $k$-tuple of points from $S$ in convex position such that the interior of their convex hull does not contain any point from $S$. For a convex body $K \subseteq \mathbb{R}^d$ of unit $d$-dimensional volume, we study the expected number $EH^K_{d,k}(n)$ of $k$-holes in a set of $n$ points drawn uniformly and independently at random from $K$. We prove an asymptotically tight lower bound on $EH^K_{d,k}(n)$ by showing that, for all fixed integers $d \geq 2$ and $k\geq d+1$, the number $EH_{d,k}^K(n)$ is at least $\Omega(n^d)$. For some small holes, we even determine the leading constant $\lim_{n \to \infty}n^{-d}EH^K_{d,k}(n)$ exactly. We improve the currently best known lower bound on $\lim_{n \to \infty}n^{-d}EH^K_{d,d+1}(n)$ by Reitzner and Temesvari (2019). In the plane, we show that the constant $\lim_{n \to \infty}n^{-2}EH^K_{2,k}(n)$ is independent of $K$ for every fixed $k \geq 3$ and we compute it exactly for $k=4$, improving earlier estimates by Fabila-Monroy, Huemer, and Mitsche (2015) and by the authors (2020). |
| ردمك: | 978-3-030-83822-5 978-3-030-83823-2 |
| تدمد: | 2297-0215 2297-024X |
| DOI: | 10.1007/978-3-030-83823-2_64 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3149ed0b06e01ad1cd51fd866ba8e34a https://doi.org/10.1007/978-3-030-83823-2_64 |
| Rights: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....3149ed0b06e01ad1cd51fd866ba8e34a |
| قاعدة البيانات: | OpenAIRE |
| ردمك: | 9783030838225 9783030838232 |
|---|---|
| تدمد: | 22970215 2297024X |
| DOI: | 10.1007/978-3-030-83823-2_64 |