Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation. (English) Zbl 1429.60068

Summary: Let us consider Euclidean first-passage percolation on the Poisson-Delaunay triangulation. We prove almost sure coalescence of any two semi-infinite geodesics with the same asymptotic direction. The proof is based on an argument of Burton-Keane type and makes use of the concentration property for shortest-path lengths in the considered graphs. Moreover, by considering the specific example of the relative neighborhood graph, we illustrate that our approach extends to further well-known graphs in computational geometry. As an application, we show that the expected number of semi-infinite geodesics starting at a given vertex and leaving a disk of a certain radius grows at most sublinearly in the radius.


60J90 Coalescent processes
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60D05 Geometric probability and stochastic geometry
Full Text: DOI arXiv Euclid


[1] Aldous, D.J. (2009). Which connected spatial networks on random points have linear route-lengths? Preprint. Available at arXiv:0911.5296 .
[2] Baccelli, F., Coupier, D. and Tran, V.C. (2013). Semi-infinite paths of the two-dimensional radial spanning tree. Adv. in Appl. Probab. 45 895-916. · Zbl 1287.60016
[3] Baccelli, F., Tchoumatchenko, K. and Zuyev, S. (2000). Markov paths on the Poisson-Delaunay graph with applications to routing in mobile networks. Adv. in Appl. Probab. 32 1-18. · Zbl 0959.60008
[4] Chenavier, N. and Devillers, O. (2015). Stretch factor of long paths in a planar Poisson-Delaunay triangulation. Preprint.
[5] Coupier, D. (2016). Sublinearity of the number of semi-infinite branches for geometric random trees. Preprint. Available at arXiv:1501.04804 . · Zbl 1390.60048
[6] Coupier, D. and Tran, V.C. (2013). The 2D-directed spanning forest is almost surely a tree. Random Structures Algorithms 42 59-72. · Zbl 1257.05159
[7] Daley, D.J. and Last, G. (2005). Descending chains, the lilypond model, and mutual-nearest-neighbour matching. Adv. in Appl. Probab. 37 604-628. · Zbl 1078.60038
[8] 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. · Zbl 0693.05045
[9] Hammersley, J.M. and Welsh, D.J.A. (1965). First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In Proc. Internat. Res. Semin. , Statist. Lab. , Univ. California , Berkeley , Calif. 61-110. New York: Springer. · Zbl 0143.40402
[10] Hirsch, C., Neuhäuser, D. and Schmidt, V. (2016). Moderate deviations for shortest-path lengths on random segment processes. ESAIM Probab. Stat. 20 261-292. · Zbl 1384.60040
[11] Howard, C.D. and Newman, C.M. (1997). Euclidean models of first-passage percolation. Probab. Theory Related Fields 108 153-170. · Zbl 0883.60091
[12] Howard, C.D. and Newman, C.M. (2001). Geodesics and spanning trees for Euclidean first-passage percolation. Ann. Probab. 29 577-623. · Zbl 1062.60099
[13] Jaromczyk, J.W. and Toussaint, G.T. (1992). Relative neighborhood graphs and their relatives. Proc. IEEE 80 1502-1517.
[14] Keil, J.M. and Gutwin, C.A. (1992). Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geom. 7 13-28. · Zbl 0751.52004
[15] Licea, C. and Newman, C.M. (1996). Geodesics in two-dimensional first-passage percolation. Ann. Probab. 24 399-410. · Zbl 0863.60097
[16] Newman, C.M. (1995). A surface view of first-passage percolation. In Proceedings of the International Congress of Mathematicians , Vol. 1, 2 ( Zürich , 1994) 1017-1023. Basel: Birkhäuser. · Zbl 0848.60089
[17] Pimentel, L.P.R. (2011). Asymptotics for first-passage times on Delaunay triangulations. Combin. Probab. Comput. 20 435-453. · Zbl 1214.60048
[18] Talagrand, M. (1995). Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. 81 73-205. · Zbl 0864.60013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.