Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-26T08:33:17.305Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  05 May 2015

DAVID ALDOUS  and
TAMAR LANDO
DAVID ALDOUS
Affiliation:
Department of Statistics, 365 Evans Hall, U.C. Berkeley CA 94220-3860, USA e-mail: [email protected]
TAMAR LANDO
Affiliation:
Department of Philosophy, Columbia University, 1150 Amsterdam Avenue, New York NY 10027, USA e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Consider a network linking the points of a rate-1 Poisson point process on the plane. Write Ψave(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 Ψave(s), and on the analogous “worst-case” function Ψworst(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 α such that each function has Ψ(s) ≍ (s − 1)−α as s ↓ 1.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 159 , Issue 1 , July 2015 , pp. 125 - 151
Copyright
Copyright © Cambridge Philosophical Society 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Aldous, D. J. Scale-invariant random spatial networks. Electron. J. Probab. 19 (2014), no. 15, 1–41.Google Scholar
[2] Aldous, D. J. and Kendall, W. S. Short-length routes in low-cost networks via Poisson line patterns. Adv. in Appl. Probab. 40 (2008), 1–21.Google Scholar
[3] Aldous, D. J. and Krikun, M. Percolating paths through random points. ALEA Lat. Am. J. Probab. Math. Stat. 1 (2006), 89–109.Google Scholar
[4] Aldous, D. J. and Shun, J. Connected spatial networks over random points and a route-length statistic. Statist. Sci. 25 (2010), 275–288.Google Scholar
[5] Bose, P., De Carufel, J.-L., Morin, P., van Renssen, A. and Verdonschot, S. Optimal bounds on theta-graphs: More is not always better. In Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG (2012), 291–296.Google Scholar
[6] Bose, P., Renssen, A. and Verdonschot, S. On the spanning ratio of theta-graphs. In Algorithms and Data Structures (Lecture Notes in Computer Science (Springer, 2013), pp. 182–194.Google Scholar
[7] Chung, F. R. K. and Graham, R. L. On Steiner trees for bounded point sets. Geom. Dedicata 11 (1981), 353–361.Google Scholar
[8] Dujmovic, V., Morin, P. and Smid, M. H. M. Average stretch factor: how low does it go? Discrete Comput. Geom. 53 (2015), 296–326.Google Scholar
[9] Keil, J. M. and Gutwin, C. A. Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geom. 7 (1992), 13–28.Google Scholar
[10] Lando, T. Efficient networks and enumerations on forests. Master's thesis. U.C. Berkeley (2008). http://www.stat.berkeley.edu/~aldous/Papers/Lando_thesis.pdf.Google Scholar
[11] Miles, R. E. On the homogeneous planar Poisson point process. Math. Biosci. 6 (1970), 85–127.Google Scholar
[12] Morin, P. and Verdonschot, S. On the average number of edges in theta graphs. http://arxiv.org/abs/1304.3402 (2013).Google Scholar
[13] Narasimhan, G. and Smid, M. Geometric Spanner Networks (Cambridge University Press, 2007).Google Scholar
[14] Preparata, F. P. and Shamos, M. I. Computational Geometry. (Springer–Verlag, 1985).Google Scholar
[15] Steele, J. M. Probability theory and combinatorial optimisation Society for Industrial and Applied Mathematics (1997).Google Scholar
[16] Stoyan, D., Kendall, W. S. and Mecke, J. Stochastic Geometry and Its Application (Wiley, 1987).Google Scholar
[17] Yao, A. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Computing 11 (1982), 721–736.Google Scholar
[18] Yukich, J. E. Probability Theory of Classical Euclidean Optimization Problems (Springer–Verlag, 1998).Google Scholar