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

The on-line nearest-neighbour graph on a sequence of nn uniform random points in (0,1)d(0,1)d (d∈Nd∈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 α∈(0,d/2]α∈(0,d/2], we prove O(max{n1−(2α/d),logn})O(max{n1−(2α/d),logn}) upper bounds on the variance. On the other hand, we give an n→∞n→∞ large-sample convergence result for the total power-weighted edge-length when α>d/2α>d/2. We prove corresponding results when the underlying point set is a Poisson process of intensity nn.