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

2023/01/06 by Mathew D. Penrose, Penrose, Mathew D., Xiaochuan Yang +1
Computer Science · Mathematics · #05C80 #60D05 #60F15 #Complexity and Algorithms in Graphs #FOS: Mathematics #Mobile Ad Hoc Networks #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2301.02506

openalex publication_date 2023/01/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let X₁,X₂, … be independent identically distributed random points in a convex polytopal domain A ⊂ ℝ^d. Define the largest nearest neighbour link L_n to be the smallest r such that every point of \mathcal X_n:=\X₁,…,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 → ∞, almost surely nL_n^d/log n tends to a limit that depends on the geometry of A, and nM_n^d/log n tends to the same limit.

Related

• Fluctuations of the connectivity threshold and largest nearest-neighbour link
• A Strong Law for the Largest Nearest-Neighbor Link on Normally Distributed Points
• Distribution of components in the k-nearest neighbour random geometric graph for k below the connectivity threshold
• Testing thresholds for high-dimensional sparse random geometric graphs
• Small components in k-nearest neighbour graphs