Short-length routes in low-cost networks via Poisson line patterns

DOI10.1239/AAP/1208358883MaRDI QIDQ5387074zbMATH OpenOpenAlexFDO

Authors David Aldous, Wilfrid S. Kendall

Publication date 15 May 2008

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0701140

zbMATH Keywords

Buffon argumentexcess statisticmark distributionPoisson line processprobabilistic methodratio statisticSlivynak theoremspatial networkSteiner treetotal variation distanceVasershtein coupling

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Geometric probability and stochastic geometry (60D05) Deterministic network models in operations research (90B10) Stochastic network models in operations research (90B15)

Abstract: In designing a network to link n cities in a square of area n, one 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 cities. Second, the average route length (taken over source-destination pairs) should not be much greater than the average straight-line distance. How small can we make these two differences? For typical configurations the shortest network length is order n and the average straight-line distance is order n^1/2, so it seems implausible that one can construct a network in which the first difference is o(n) and the second difference is o(n^1/2). But in fact one can do better: for an arbitrary configuration one can construct a network where the first difference is o(n) and the second difference is almost as small as O(log n). The construction is conceptually simple: over the minimum-length connected network (Steiner tree) superimpose a sparse stationary and isotropic Poisson line process. The key ingredient is a new result about the Poisson line process. Consider two points at 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 2r + C log r. Turning to lower bounds we show that, under a weak equidistribution assumption, if the first difference is O(n) then the second difference cannot be o(sqrt(log n)).

Recommendations

• Efficient routeing in Poisson small-world networks
• Minimum Cost Routing on Stochastic Networks
• Optimal scale-free compact routing schemes in networks of low doubling dimension
• Minimum-cost line broadcast in paths
• Shortest paths in networks with exponentially distributed arc lengths
• Shortest-Path Routing in Arbitrary Networks
• Scale-free compact routing schemes in networks of low doubling dimension
• A novel linear algorithm for shortest paths in networks
• Cheapest paths in dynamic networks

Cites work

• A heuristic proof of a long-standing conjecture of D. G. Kendall concerning the shapes of certain large random polygons
• A simplified proof of a conjecture of D. G. Kendall concerning shapes of random polygons
• Conformal invariance of planar loop-erased random walks and uniform spanning trees.
• scientific article; zbMATH DE number 4009416 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Probability theory of classical Euclidean optimization problems
• Proof of David Kendall's conjecture concerning the shape of large random polygons
• The limit shape of the zero cell in a stationary Poisson hyperplane tessellation.

Cited in

(17)

• Spatial Gibbs random graphs
• Route lengths in invariant spatial tree networks
• Phase transitions and percolation at criticality in enhanced random connection models
• A conversation with David J. Aldous
• Shape theorem and surface fluctuation for Poisson cylinders
• Average stretch factor: how low does it go?
• Analysis of shortest paths and subscriber line lengths in telecommunication access networks
• Scaling limits for shortest path lengths along the edges of stationary tessellations
• Asymptotics of geometrical navigation on a random set of points in the plane
• Improper Poisson line process as SIRSN in any dimension
• Continuity results and estimates for the Lyapunov exponent of Brownian motion in stationary potential
• Spatial transportation networks with transfer costs: asymptotic optimality of hub-and-spoke models
• Return to the Poissonian city
• First passage percolation on random geometric graphs and an application to shortest-path trees
• The stretch-length tradeoff in geometric networks: average case and worst case study
• Geodesics and flows in a Poissonian city
• Connected spatial networks over random points and a route-length statistic

This page was built for publication: Short-length routes in low-cost networks via Poisson line patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387074)