Connected Spatial Networks over Random Points and a Route-Length Statistic
Authors:
- David J. AldousDADavid J. Aldous
- Julian ShunJSJulian Shun
Open Access
- 1 August 2010
- journal article
- Published by Institute of Mathematical Statistics in Statistical Science
- Vol. 25 (3) , 275-288
Abstract
We review mathematically tractable models for connected networks on random points in the plane, emphasizing the class of proximity graphs which deserves to be better known to applied probabilists and statisticians. We introduce and motivate a particular statistic R measuring shortness of routes in a network. We illustrate, via Monte Carlo in part, the trade-off between normalized network length and R in a one-parameter family of proximity graphs. How close this family comes to the optimal trade-off over all possible networks remains an intriguing open question. The paper is a write-up of a talk developed by the first author during 2007–2009.Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Short-length routes in low-cost networks via Poisson line patternsAdvances in Applied Probability, 2008
- Estimating the asymptotic constants of the total length of Euclidean minimal spanning trees with power-weighted edgesStatistics & Probability Letters, 2000
- Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networksAdvances in Applied Probability, 2000
- The central limit theorem for Euclidean minimal spanning trees IIAdvances in Applied Probability, 1999
- The central limit theorem for weighted minimal spanning trees on random pointsThe Annals of Applied Probability, 1996
- Hammersley's interacting particle process and longest increasing subsequencesProbability Theory and Related Fields, 1995
- On Central Limit Theorems in Geometrical ProbabilityThe Annals of Applied Probability, 1993
- Asymptotics for Euclidean minimal spanning trees on random pointsProbability Theory and Related Fields, 1992
- The Minimum Spanning Tree Constant in Geometrical Probability and Under the Independent Model: A Unified ApproachThe Annals of Applied Probability, 1992
- Properties of Gabriel Graphs Relevant to Geographic Variation Research and the Clustering of Points in the PlaneGeographical Analysis, 1980