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

AR Wade

Research output: Contribution to journalArticle (Academic Journal)peer-review

7 Citations (Scopus)

Abstract

The on-line nearest-neighbour graph on a sequence of $n$ uniform random points in $(0,1)^d$ ($d \in \N$) 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 $\alpha \in (0,d/2]$, we prove $O(\max \{n^{1-(2\alpha/d)}, \log n \})$ upper bounds on the variance. On the other hand, we give an $n \to \infty$ large-sample convergence result for the total power-weighted edge-length when $\alpha > d/2$. We prove corresponding results when the underlying point set is a Poisson process of intensity $n$.
Translated title of the contributionAsymptotic theory for the multidimensional random on-line nearest-neighbour graph
Original languageEnglish
Pages (from-to)1889 - 1911
Number of pages23
JournalStochastic Processes and their Applications
Volume119
DOIs
Publication statusPublished - Jun 2009

Bibliographical note

Publisher: Elsevier

Fingerprint

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

Cite this