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

Mathew D. Penrose, Andrew R. Wade

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)
54 Downloads (Pure)


In the on-line nearest-neighbour graph (ONG), each point after the first in a sequence of points in Rd is joined by an edge to its nearest neighbour amongst those points that precede it in the sequence. We study the large-sample asymptotic behaviour 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 > 1/2, the limiting distribution of the centred 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-neighbour (directed) graph on uniform random points in the unit interval.
Original languageEnglish
Pages (from-to)125-156
Number of pages32
JournalRandom Structures and Algorithms
Issue number2
Publication statusPublished - 13 Aug 2007


  • nearest-neighbour graph
  • spatial network evolution
  • weak convergence
  • fixed-point equation
  • divide-and-conquer


Dive into the research topics of 'Limit theory for the random on-line nearest-neighbour graph'. Together they form a unique fingerprint.

Cite this