Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-15T10:34:07.898Z Has data issue: false hasContentIssue false
  • English
  • Français

Stretch factor in a planar Poisson–Delaunay triangulation with a large intensity

Part of:Geometric probability and stochastic geometryGraph theory

Published online by Cambridge University Press:  20 March 2018

Nicolas Chenavier and
Olivier Devillers
Nicolas Chenavier*
Affiliation:
Université du Littoral Côte d'Opale
Olivier Devillers*
Affiliation:
INRIA, CNRS, Université de Lorraine
*
* Postal address: LMPA Joseph Liouville, Université du Littoral Côte d'Opale, 50 rue Ferdinand Buisson, BP 699, 62228 Calais Cedex, France. Email address: nicolas.chenavier@univ-littoral.fr
** Postal address: Université de Lorraine, 615 rue du Jardin Botanique, B.P. 101, 54602 Villers-lès-Nancy Cedex, France. Email address: olivier.devillers@inria.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let X := X n ∪ {(0, 0), (1, 0)}, where X n is a planar Poisson point process of intensity n. We provide a first nontrivial lower bound for the distance between the expected length of the shortest path between (0, 0) and (1, 0) in the Delaunay triangulation associated with X when the intensity of X n goes to ∞. Simulations indicate that the correct value is about 1.04. We also prove that the expected length of the so-called upper path converges to 35 / 3π2, yielding an upper bound for the expected length of the smallest path.

Keywords

Delaunay triangulationPoisson point processstretch factor

MSC classification

Primary:60D05: Geometric probability and stochastic geometry05C80: Random graphs

Information

Type
Original Article
Information
Advances in Applied Probability , Volume 50 , Issue 1 , March 2018, pp. 35 - 56
Copyright
Copyright © Applied Probability Trust 2018 

References

[1] Aurenhammer, F., Klein, R. and Lee, D.-T. (2013). Voronoi Diagrams and Delaunay Triangulations. World Scientific, Hackensack, NJ. CrossRefGoogle Scholar
[2] Baccelli, F., Tchoumatchenko, K. and Zuyev, S. (2000). Markov paths on the Poisson-Delaunay graph with applications to routing in mobile networks. Adv. Appl. Prob. 32, 1–18. Google Scholar
[3] Bose, P. and Devroye, L. (2007). On the stabbing number of a random Delaunay triangulation. Comput. Geom. 36, 89–105. Google Scholar
[4] Bose, P. and Morin, P. (2004). Online routing in triangulations. SIAM J. Comput. 33, 937–951. Google Scholar
[5] Calka, P. (2002). The distributions of the smallest disks containing the Poisson-Voronoi typical cell and the Crofton cell in the plane. Adv. Appl. Prob. 34, 702–717. Google Scholar
[6] Cazals, F. and Giesen, J. (2006). Delaunay triangulation based surface reconstruction. In Effective Computational Geometry for Curves and Surfaces, Springer, Berlin, pp. 231–276. Google Scholar
[7] Chenavier, N. and Devillers, O. (2016). Stretch factor of long paths in a planar Poisson-Delaunay triangulation. Res. Rep. 8935, INRIA. Google Scholar
[8] Cheng, S.-W., Dey, T. K. and Shewchuk, J. R. (2013). Delaunay Mesh Generation. Chapman & Hall/CRC, Boca Raton, FL. Google Scholar
[9] Cox, J. T., Gandolfi, A., Griffin, P. S. and Kesten, H. (1993). Greedy lattice animals. I. Upper bounds. Ann. Appl. Prob. 3, 1151–1169. Google Scholar
[10] De Castro, P. M. M. and Devillers, O. (2018). Expected length of the Voronoi path in a high dimensional Poisson–Delaunay triangulation. Discrete Comput. Geom. 1–20. Available at https://doi.org/10.1007/s00454-017-9866-y. Google Scholar
[11] Devillers, O. and Hemsley, R. (2016). The worst visibility walk in random Delaunay triangulation is O(√n). J. Comput. Geom. 7, 332–359. Google Scholar
[12] Devillers, O. and Noizet, L. (2016). Walking in a planar Poisson-Delaunay triangulation: shortcuts in the Voronoi path. Res. Rep. 8946, INRIA. Google Scholar
[13] Devillers, O., Pion, S. and Teillaud, M. (2002). Walking in a triangulation. Internat. J. Found. Comput. Sci. 13, 181–199. CrossRefGoogle Scholar
[14] Devroye, L., Lemaire, C. and Moreau, J.-M. (2004). Expected time analysis for Delaunay point location. Comput. Geom. 29, 61–89. Google Scholar
[15] Dobkin, D. P., Friedman, S. J. and Supowit, K. J. (1990). Delaunay graphs are almost as good as complete graphs. Discrete Comput. Geom. 5, 399–407. CrossRefGoogle Scholar
[16] Gerard, Y., Vacavant, A. and Favreau, J.-M. (2016). Tight bounds in the quadtree complexity theorem and the maximal number of pixels crossed by a curve of given length. Theoret. Comput. Sci. 624, 41–55. CrossRefGoogle Scholar
[17] Hirsch, C., Neuhä;user, D. and Schmidt, V. (2016). Moderate deviations for shortest-path lengths on random segment processes. ESAIM Prob. Statist. 20, 261–292. CrossRefGoogle Scholar
[18] Keil, J. M. and Gutwin, C. A. (1989). The Delaunay triangulation closely approximates the complete Euclidean graph. In Algorithms and Data Structures (Lecture Notes Comput. Sci. 382), Springer, Berlin, pp. 47–56. Google Scholar
[19] Penrose, M. (2003). Random Geometric Graphs. Oxford University Press. Google Scholar
[20] Schneider, R. and Weil, W. (2008). Stochastic and Integral Geometry. Springer, Berlin. CrossRefGoogle Scholar
[21] Thä;le, C. and Yukich, J. E. (2016). Asymptotic theory for statistics of the Poisson-Voronoi approximation. Bernoulli 22, 2372–2400. Google Scholar
[22] Xia, G. (2013). The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. Comput. 42, 1620–1659. Google Scholar
[23] Xia, G. and Zhang, L. (2011). Toward the tight bound of the stretch factor of Delaunay triangulations. In Proceedings 23th Canadian Conference on Computational Geometry, 6 pp. Google Scholar
[24] Yukich, J. E. (2015). Surface order scaling in stochastic geometry. Ann. Appl. Prob. 25, 177–210. Google Scholar