Penrose, M.D. and Wade, A.R. (2008) Limit theory for the random online nearestneighbour graph. Random Structures and Algorithms, 32 (2). pp. 125156. ISSN 10429832

PDF (strathprints013396.pdf)
strathprints013396.pdf Download (407kB)  Preview 
Abstract
In the online nearestneighbour 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 largesample asymptotic behaviour of the total powerweighted 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 nearestneighbour (directed) graph on uniform random points in the unit interval.
Item type:  Article 

ID code:  13396 
Keywords:  nearestneighbour graph, spatial network evolution, weak convergence, fixedpoint equation, divideandconquer, Probabilities. Mathematical statistics, Mathematics, Computer Graphics and ComputerAided Design, Software, Applied Mathematics, Mathematics(all) 
Subjects:  Science > Mathematics > Probabilities. Mathematical statistics Science > Mathematics 
Department:  Faculty of Science > Mathematics and Statistics 
Depositing user:  Mrs Carolynne Westwood 
Date Deposited:  12 Nov 2009 14:14 
Last modified:  26 Mar 2015 16:35 
URI:  http://strathprints.strath.ac.uk/id/eprint/13396 
Actions (login required)
View Item 