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

The on-line nearest-neighbour graph on a sequence of n uniform random points in (0, 1)(d) (d is an element of N) 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 is an element of (0, d/2], we prove O (max{n (1-(2 alpha/d)), log n}) upper bounds on the variance. On the other hand, we give an n -> infinity 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. (C) 2008 Elsevier B.V. All rights reserved.