Tight bounds on the expected number of holes in random point sets. Issue 1 (21st April 2022)

• Record Type: Journal Article
• Authors: Balko, Martin; Scheucher, Manfred; Valtr, Pavel
• Is Part Of: Random structures & algorithms. Volume 62:Issue 1(2023)
• Page Start: 29
• Page End: 51
• Publication Date: 2022-04-21
• Subjects: convex position -- k‐hole -- random point set -- stochastic geometry; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21088
• Languages: English
• ISSNs: 1042-9832

Abstract

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 E H d, k K ( 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 E H d, k K ( 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 E H d, k K ( n ) $$ E{H}_{d, k}^K(n) $$ is at least Ω ( n d ) $$ \Omega \left({n}^d\right) $$ . For some small holes, we even determine the leading constant lim n → ∞ n − d E H d, k K ( n ) $$ {\lim}_{n\to \infty }{n}^{-d}E{H}_{d, k}^K(n) $$ exactly. We improve the currently best‐known lower bound on lim n → ∞ n − d E H d, d + 1 K ( 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 lim n → ∞ n − 2 E H 2, k K ( 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.