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

DOI10.1017/S0305004115000250zbMATH Open1371.60085arXiv1404.2653OpenAlexW2962785303MaRDI QIDQ5360331FDOQ5360331

Authors: David Aldous, Tamar Lando 

Publication date: 28 September 2017

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

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$.

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

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

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)

Cites Work

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

Cited In (2)

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

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)