### Abstract

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 language | English |
---|---|

Pages (from-to) | 1889-1911 |

Number of pages | 22 |

Journal | Stochastic Processes and their Applications |

Volume | 119 |

Issue number | 6 |

DOIs | |

Publication status | Published - Jun 2009 |

### Keywords

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

## Cite this

Wade, A. R. (2009). Asymptotic theory for the multidimensional random on-line nearest-neighbour graph.

*Stochastic Processes and their Applications*,*119*(6), 1889-1911. https://doi.org/10.1016/j.spa.2008.09.006