Penrose, M.D. and Wade, A.R. (2008) *Limit theory for the random on-line nearest-neighbour graph.* Random Structures and Algorithms, 32 (2). pp. 125-156. ISSN 1042-9832

## 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.

Item type: | Article |

ID code: | 13396 |

Keywords: | nearest-neighbour graph, spatial network evolution, weak convergence, fixed-point equation, divide-and-conquer, Probabilities. Mathematical statistics, Mathematics, Computer Graphics and Computer-Aided Design, Software, Applied Mathematics, Mathematics(all) |

Subjects: | Science > Mathematics > Probabilities. Mathematical statistics Science > Mathematics |

Department: | Faculty of Science > Mathematics and Statistics |

Related URLs: | |

Depositing user: | Mrs Carolynne Westwood |

Date Deposited: | 12 Nov 2009 14:14 |

Last modified: | 04 Sep 2014 23:45 |

URI: | http://strathprints.strath.ac.uk/id/eprint/13396 |
---|

### Actions (login required)