Penrose, Mathew D. and Wade, Andrew R. (2008) 'Limit theory for the random on-line nearest-neighbor graph.', Random structures and algorithms., 32 (2). pp. 125-156.
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.
| Item Type: | Article |
|---|---|
| Keywords: | Nearest-neighbor graph,Spatial network evolution, Weak convergence, Fixed-point equation, Divide-and-conquer. |
| Full text: | Full text not available from this repository. |
| Publisher Web site: | http://dx.doi.org/10.1002/rsa.20185 |
| Date accepted: | No date available |
| Date deposited: | No date available |
| Date of first online publication: | March 2008 |
| Date first made open access: | No date available |
Save or Share this output
| Export: | |
| Look up in GoogleScholar |
