### Abstract

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

Pages (from-to) | 125-156 |

Number of pages | 32 |

Journal | Random Structures and Algorithms |

Volume | 32 |

Issue number | 2 |

DOIs | |

Publication status | Published - 13 Aug 2007 |

### Keywords

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

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

## Cite this

Penrose, M. D., & Wade, A. R. (2007). Limit theory for the random on-line nearest-neighbour graph.

*Random Structures and Algorithms*,*32*(2), 125-156. https://doi.org/10.1002/rsa.20185