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

MD Penrose, AR Wade

Research output: Contribution to journalArticle (Academic Journal)

8 Citations (Scopus)

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 $\alpha>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.
Translated title of the contributionLimit theory for the random on-line nearest-neighbour graph
Original languageEnglish
Pages (from-to)125 - 156
Number of pages32
JournalRandom Structures and Algorithms
Volume32 (2)
DOIs
Publication statusPublished - Mar 2008

Bibliographical note

Publisher: Wiley

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