2006/03/31 by Andrew R. Wade · 23 citations
Mathematics · #Constant (computer programming) #Generality #Law of large numbers #Limiting #Limits and Structures in Graph Theory #Point (geometry) #Random Matrices and Applications #Random graph #Stochastic processes and statistical mechanics #math.PR #msc:60D05 #msc:60F25
paper · pdf · doi:10.1239/aap/1183667613
published in Advances in Applied Probability 39(2), 326-342 (Cambridge University Press) · 18 pages, 2 figures; revised presentation
arxiv created 2007/02/14 · openalex publication_date 2007/06/01 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Under the unifying umbrella of a general result of Penrose and Yukich ( Annals of Applied Probability 13 (2003), 277-303) we give laws of large numbers (in the L p sense) for the total power-weighted length of several nearest-neighbour-type graphs on random point sets in ℝ d , d ∈ ℕ. Some of these results are known; some are new. We give limiting constants explicitly, where previously they have been evaluated in less generality or not at all. The graphs we consider include the k -nearest-neighbours graph, the Gabriel graph, the minimal directed spanning forest, and the on-line nearest-neighbour graph.