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

Abstract

The on-line nearest-neighbour graph on a sequence of $n$ uniform random points in $(0,1{)}^d$ ($d\in \mathbb{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$.

25 pages; v2: substantial revision, change in title, central limit theorem present in v1 removed due to a gap

References in corpus (3)

• Gaussian limits for random measures in geometric probability
• Explicit laws of large numbers for random nearest-neighbour type graphs
• Limit theory for the random on-line nearest-neighbour graph