The stretch-length tradeoff in geometric networks: average case and worst case study

DOI10.1017/S0305004115000250MaRDI QIDQ5360331zbMATH OpenOpenAlexFDO

Authors David Aldous, Tamar Lando

Publication date 28 September 2017

Published in Mathematical Proceedings of the Cambridge Philosophical Society (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Point processes (e.g., Poisson, Cox, Hawkes processes) (60G55) Geometric probability and stochastic geometry (60D05) Deterministic network models in operations research (90B10)

Abstract: Consider a network linking the points of a rate-$1$ Poisson point process on the plane. Write $Ps{i}^{mboxave}(s)$ for the minimum possible mean length per unit area of such a network, subject to the constraint that the route-length between every pair of points is at most $s$ times the Euclidean distance. We give upper and lower bounds on the function $Ps{i}^{mboxave}(s)$, and on the analogous "worst-case" function $Ps{i}^{mboxworst}(s)$ where the point configuration is arbitrary subject to average density one per unit area. Our bounds are numerically crude, but raise the question of whether there is an exponent $alpha$ such that each function has $Psi(s)asymp(s-1{)}^{-alpha}$ as $sdownarrow1$.

Recommendations

• Average stretch factor: how low does it go?
• Short-length routes in low-cost networks via Poisson line patterns
• scientific article; zbMATH DE number 6313173
• Route lengths in invariant spatial tree networks
• Connected spatial networks over random points and a route-length statistic

Cites work

• scientific article; zbMATH DE number 4009416 (Why is no real title available?)
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Average stretch factor: how low does it go?
• Classes of graphs which approximate the complete Euclidean graph
• Connected spatial networks over random points and a route-length statistic
• Geometric Spanner Networks
• On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
• On Steiner trees for bounded point sets
• On the average number of edges in theta graphs
• On the homogeneous planar Poisson point process
• On the spanning ratio of theta-graphs
• Percolating paths through random points
• Probability theory of classical Euclidean optimization problems
• Scale-invariant random spatial networks
• Short-length routes in low-cost networks via Poisson line patterns
• Towards tight bounds on theta-graphs: more is not always better

Cited in

(2)

• Connected spatial networks over random points and a route-length statistic
• Route lengths in invariant spatial tree networks

This page was built for publication: The stretch-length tradeoff in geometric networks: average case and worst case study

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