Largest nearest-neighbour link and connectivity threshold in a polytopal random sample

Abstract

Let $X_1,X_2,\dots$ be independent identically distributed random points in a convex polytopal domain $A\subset {\mathbb{R}}^d$. Define the largest nearest neighbour link $L_n$ to be the smallest $r$ such that every point of ${\mathcal{X}}_n:=\{X_1,\dots ,X_n\}$ has another such point within distance $r$. We obtain a strong law of large numbers for $L_n$ in the large-$n$ limit. A related threshold, the connectivity threshold $M_n$, is the smallest $r$ such that the random geometric graph $G({\mathcal{X}}_n,r)$ is connected. We show that as $n\to \infty$, almost surely $n{L}_n^d/\log n$ tends to a limit that depends on the geometry of $A$, and $n{M}_n^d/\log n$ tends to the same limit.

arXiv comment26 pages