Tight bounds on the expected number of holes in random point sets

M Balko, M Scheucher, P Valtr - Random Structures & …, 2023 - Wiley Online Library
M Balko, M Scheucher, P Valtr
Random Structures & Algorithms, 2023Wiley Online Library
For integers d≥ 2 d ≥ 2 and k≥ d+ 1 k ≥ d+ 1, ak k‐hole in a set SS of points in general
position in ℝ d R^ d is ak k‐tuple of points from SS in convex position such that the interior of
their convex hull does not contain any point from S S. For a convex body K⊆ ℝ d K ⊆ R^ d
of unit dd‐dimensional volume, we study the expected number EH d, k K (n) EH _ d, k^ K (n)
of kk‐holes in a set of nn points drawn uniformly and independently at random from K K. We
prove an asymptotically tight lower bound on EH d, k K (n) EH _ d, k^ K (n) by showing that …
Abstract
For integers d≥2$$ d\ge 2 $$ and k≥d+1$$ k\ge d+1 $$, a k$$ k $$‐hole in a set S$$ S $$ of points in general position in ℝd$$ {\mathbb{R}}^d $$ is a k$$ k $$‐tuple of points from S$$ S $$ in convex position such that the interior of their convex hull does not contain any point from S$$ S $$. For a convex body K⊆ℝd$$ K\subseteq {\mathbb{R}}^d $$ of unit d$$ d $$‐dimensional volume, we study the expected number EHd,kK(n)$$ E{H}_{d,k}^K(n) $$ of k$$ k $$‐holes in a set of n$$ n $$ points drawn uniformly and independently at random from K$$ K $$. We prove an asymptotically tight lower bound on EHd,kK(n)$$ E{H}_{d,k}^K(n) $$ by showing that, for all fixed integers d≥2$$ d\ge 2 $$ and k≥d+1$$ k\ge d+1 $$, the number EHd,kK(n)$$ E{H}_{d,k}^K(n) $$ is at least Ω(nd)$$ \Omega \left({n}^d\right) $$. For some small holes, we even determine the leading constant limn→∞n−dEHd,kK(n)$$ {\lim}_{n\to \infty }{n}^{-d}E{H}_{d,k}^K(n) $$ exactly. We improve the currently best‐known lower bound on limn→∞n−dEHd,d+1K(n)$$ {\lim}_{n\to \infty }{n}^{-d}E{H}_{d,d+1}^K(n) $$ by Reitzner and Temesvari (2019). In the plane, we show that the constant limn→∞n−2EH2,kK(n)$$ {\lim}_{n\to \infty }{n}^{-2}E{H}_{2,k}^K(n) $$ is independent of K$$ K $$ for every fixed k≥3$$ k\ge 3 $$ and we compute it exactly for k=4$$ k=4 $$, improving earlier estimates by Fabila‐Monroy, Huemer, and Mitsche and by the authors.
Wiley Online Library