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

Abstract

Let X1, X2, . . . be independent identically distributed random points in a convex polytopal domain A ⊂ Rd . Define the largest nearest-neighbour link Ln to be the smallest r such that every point of Xn := {X1, . . . , Xn} has another such point within distance r .We obtain a strong law of large numbers for Ln in the large-n limit. A related threshold, the connectivity threshold Mn, is the smallest r such that the random geometric graph G(Xn, r ) is connected (so Ln ≤ Mn). We show that as n→∞, almost surely nLdn / log n tends to a limit that depends on the geometry of A, and nMd n / log n tends to the same limit. We derive these results via asymptotic lower bounds for Ln and upper bounds for Mn that are applicable in a larger class of metric spaces satisfying certain regularity conditions.