Explicit laws of large numbers for random nearest-neighbour type graphs

Abstract

Under the unifying umbrella of a general result of Penrose & Yukich [Ann. Appl. Probab., (2003) 13, 277--303] we give laws of large numbers (in the $L^p$ sense) for the total power-weighted length of several nearest-neighbour type graphs on random point sets in ${\mathbb{R}}^d$, $d\in \mathbb{N}$. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k-nearest neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.

18 pages, 2 figures; revised presentation

Cited by in corpus (7)

• Laws of large numbers in stochastic geometry with statistical applications
• Detection of Gauss-Markov Random Fields with Nearest-Neighbor Dependency
• Limit theory for point processes in manifolds
• Asymptotic theory for the multidimensional random on-line nearest-neighbour graph
• Limit theory for the random on-line nearest-neighbour graph
• Multivariate normal approximation in geometric probability
• On the Distribution of the Number of Copies of Weakly Connected Digraphs in Random $k$NN Digraphs