The Library
Shortlength routes in lowcost networks via Poisson line patterns
Tools
Aldous, D. J. (David J.) and Kendall, Wilfrid S.. (2008) Shortlength routes in lowcost networks via Poisson line patterns. Advances in Applied Probability, Vol.40 (No.1). pp. 121. ISSN 00018678

PDF
WRAP_Kendall_AldousKendall2007.pdf  Submitted Version  Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (416Kb) 
Official URL: http://dx.doi.org/10.1239/aap/1208358883
Abstract
In designing a network to link n points in a square of area n, we might be guided by the following two desiderata. First, the total network length should not be much greater than the length of the shortest network connecting all points. Second, the average route length (taken over sourcedestination pairs) should not be much greater than the average straightline distance. How small can we make these two excesses? Speaking loosely, for a nondegenerate configuration, the total network length must be at least of order n and the average straightline distance must be at least of order n(1/2), so it seems implausible that a single network might exist in which the excess over the first minimum is o(n) and the excess over the second minimum is o(n(1/2)). But in fact we can do better: for an arbitrary configuration, we can construct a network where the first excess is o(n) and the second excess is almost as small as O(log n). The construction is conceptually simple and uses stochastic methods: over the minimumlength connected network (Steiner tree) superimpose a sparse stationary and isotropic Poisson line process. Together with a few additions (required for technical reasons), the mean values of the excess for the resulting random network satisfy the above asymptotics; hence, a standard application of the probabilistic method guarantees the existence of deterministic networks as required (speaking constructively, such networks can be constructed using simple rejection sampling). The key ingredient is a new result about the Poisson line process. Consider two points a distance r apart, and delete from the line process all lines which separate these two points. The resulting pattern of lines partitions the plane into cells; the cell containing the two points has mean boundary length approximately equal to 2r + constant(logr). Turning to lower bounds, consider a sequence of networks in [0, root n](2) satisfying a weak equidistribution assumption. We show that if the first excess is O(n) then the second excess cannot be o(root log n).
Item Type:  Journal Article 

Subjects:  Q Science > QA Mathematics 
Divisions:  Faculty of Science > Statistics 
Library of Congress Subject Headings (LCSH):  System analysis, Poisson processes 
Journal or Publication Title:  Advances in Applied Probability 
Publisher:  Applied Probability Trust 
ISSN:  00018678 
Date:  March 2008 
Volume:  Vol.40 
Number:  No.1 
Number of Pages:  21 
Page Range:  pp. 121 
Identification Number:  10.1239/aap/1208358883 
Status:  Peer Reviewed 
Publication Status:  Published 
Access rights to Published version:  Restricted or Subscription Access 
Funder:  National Science Foundation (U.S.) (NSF) 
Grant number:  DMS0203062 (NSF) 
References:  Gastner, M. T. and M. E. J. Newman (2006). Shape and efficiency in spatial distribution networks. Journal of Statistical Mechanics: Theory and Experiment 2006(01), P01015. Hug, D., M. Reitzner, and R. Schneider (2004). The limit shape of the zero cell in a stationary Poisson hyperplane tessellation. Ann. Probab. 32(1B), 1140–1167. Kovalenko, I. (1997). A proof of a conjecture of David Kendall on the shape of random polygons of large area. Kibernet. Sistem. Anal. (4), 3–10, 187. English translation: Cybernet. Systems Anal. 33 461467. Kovalenko, I. N. (1999). A simplified proof of a conjecture of D. G. Kendall concerning shapes of random polygons. J. Appl. Math. Stochastic Anal. 12(4), 301– 310. Lawler, G. F., O. Schramm, and W. Werner (2004). Conformal invariance of planar looperased random walks and uniform spanning trees. Ann. Probab. 32(1B), 939–995. Miles, R. E. (1995). A heuristic proof of a longstanding conjecture of D. G. Kendall concerning the shapes of certain large random polygons. Adv. Appl. Probab. 27(2), 397–417. Read, N. (2005). Minimum spanning trees and random resistor networks in d dimensions. Phys. Rev. E (3) 72(3), 036114, 17. Steele, J. M. (1997). Probability theory and combinatorial optimization, Volume 69 of CBMSNSF Regional Conference Series in Applied Mathematics. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). Stoyan, D., W. S. Kendall, and J. Mecke (1995). Stochastic geometry and its applications (Second ed.). Chichester: John Wiley & Sons. (First edition in 1987 joint with Akademie Verlag, Berlin). Yukich, J. E. (1998). Probability theory of classical Euclidean optimization problems, Volume 1675 of Lecture Notes in Mathematics. Berlin: SpringerVerlag. 
URI:  http://wrap.warwick.ac.uk/id/eprint/30042 
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
View Item 