Limit theory for the random on-line nearest-neighbor graph

In the on-line nearest-neighbor graph (ONG), each point after the first in a sequence of points in R-d is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large-sample asymptotic behavior of the total power-weighted length of the ONG on uniform random points in (0, 1)(d). In particular, for d = 1 and weight exponent alpha > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed-point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest-neighbor (directed) graph on uniform random points in the unit interval. (c) 2007 Wiley Periodicals, Inc.