Asymptotic theory for the multidimensional random on-line nearest-neighbour graph

Andrew R. Wade

Stochastic Processes and their Applications, 119, no. 6, June 2009, 1889–1911. DOI: 10.1016/j.spa.2008.09.006.

Abstract

The on-line nearest-neighbour graph on a sequence of n uniform random points in $(0,1)^d$ joins each point after the first to its nearest neighbour amongst its predecessors. For the total power-weighted edge-length of this graph, with weight exponent $\alpha \in (0,d/2)$, we prove $O( \max \{ n^{-2\alpha/d} , \log n \} )$ upper bounds on the variance. On the other hand, we give a large-sample convergence result for the total power-weighted edge-length when $\alpha > d/2$. We prove corresponding results when the underlying point set is a Poisson process of intensity $n$.