WIAS Preprint No. 2243, (2016)

Coalescence of Euclidean geodesics on the Poisson--Delaunay triangulation


  • Coupier, David
  • Hirsch, Christian

2010 Mathematics Subject Classification

  • 60D05


  • coalescence, Burton-Keane argument, Delaunay triangulation, relative neighborhood graph, Poisson point process, first-passage percolation, sublinearity




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 adapted Burton-Keane argument 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.

Appeared in

  • Bernoulli, 24 (2018), pp. 2721--2751.

Download Documents