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

Andrew R. Wade

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)
50 Downloads (Pure)


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 αset membership, variant(0,d/2], we prove O(max{n1−(2α/d),logn}) upper bounds on the variance. On the other hand, we give an n→∞ large-sample convergence result for the total power-weighted edge-length when α>d/2. We prove corresponding results when the underlying point set is a Poisson process of intensity n.
Original languageEnglish
Pages (from-to)1889-1911
Number of pages22
JournalStochastic Processes and their Applications
Issue number6
Publication statusPublished - Jun 2009


  • random spatial graphs
  • network evolution
  • variance asymptotics
  • martingale dierences
  • statistics

Cite this