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

Andrew R. Wade

Advances in Applied Probability, 39, no. 2, June 2007, 326–342. DOI: 10.1239/aap/1183667613. [Article] [arXiv] [MR]



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 \geq 1$. 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.