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

Penrose, Mathew D.; Wade, Andrew R.

Abstract

In the on-line nearest-neighbor graph (ONG), each point after the first in a sequence of points in ℝd is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large-sample asymptotic behavior 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 centered 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-neighbor (directed) graph on uniform random points in the unit interval.

Citation

Penrose, M. D., & Wade, A. R. (2008). Limit theory for the random on-line nearest-neighbor graph. Random Structures and Algorithms, 32(2), 125-156. https://doi.org/10.1002/rsa.20185

• Journal Article Type: Article
• Publication Date: Mar 1, 2008
• Deposit Date: Oct 4, 2012
• Journal: Random Structures and Algorithms
• Print ISSN: 1042-9832
• Electronic ISSN: 1098-2418
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 32
• Issue: 2
• Pages: 125-156
• DOI: https://doi.org/10.1002/rsa.20185
• Keywords: Nearest-neighbor graph,Spatial network evolution, Weak convergence, Fixed-point equation, Divide-and-conquer.
• Public URL: https://durham-repository.worktribe.com/output/1472565