Connected Spatial Networks over Random Points and a Route-Length Statistic
arXiv:1003.3700 · doi:10.1214/10-STS335
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 measuring shortness of routes in a network. We illustrate, via Monte Carlo in part, the trade-off between normalized network length and 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.
Published in at http://dx.doi.org/10.1214/10-STS335 the Statistical Science (http://www.imstat.org/sts/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (5)
Cited by in corpus (13)
- Emergence of hierarchy in cost driven growth of spatial networks
- Local impacts on road networks and access to critical locations during extreme floods
- Interacting particle systems as stochastic social dynamics
- Scale-Invariant Random Spatial Networks
- The shape of shortest paths in random spatial networks
- Central loops in random planar graphs
- Betweenness centrality in dense spatial networks
- Exploring the relationship between the spatial distribution of roads and universal pattern of travel-route efficiency in urban road networks
- Towards a classification of planar maps
- Spatial Strength Centrality and the Effect of Spatial Embeddings on Network Architecture
- How much longer do you have to drive than the crow has to fly?
- Decentralized Routing on Spatial Networks with Stochastic Edge Weights
- The Stretch - Length Tradeoff in Geometric Networks: Average Case and Worst Case Study