Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

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

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

[img]
Preview
PDF (strathprints013396.pdf)
strathprints013396.pdf - Accepted Author Manuscript

Download (407kB) | Preview

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.