Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation

DOI10.3150/17-BEJ943zbMATH Open1429.60068arXiv1603.05171OpenAlexW2798853240MaRDI QIDQ1708982FDOQ1708982

Authors: David Coupier, Christian Hirsch 

Publication date: 27 March 2018

Published in: Bernoulli (Search for Journal in Brave)

Abstract: 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.

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

Recommendations

• Coalescence of geodesics in exactly solvable models of last passage percolation
• Publication:4938896
• Geodesics in two-dimensional first-passage percolation
• Geodesics and spanning trees for Euclidean first-passage percolation.
• scientific article; zbMATH DE number 17688

zbMATH Keywords

coalescenceDelaunay triangulationPoisson point processfirst-passage percolationsublinearityrelative neighborhood graphBurton-Keane argument

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Coalescent processes (60J90)

Cites Work

• Geodesics and spanning trees for Euclidean first-passage percolation.
• Title not available (Why is that?)
• Concentration of measure and isoperimetric inequalities in product spaces
• Delaunay graphs are almost as good as complete graphs
• Title not available (Why is that?)
• Classes of graphs which approximate the complete Euclidean graph
• Descending chains, the lilypond model, and mutual-nearest-neighbour matching
• Euclidean models of first-passage percolation
• Geodesics in two-dimensional first-passage percolation
• The 2D-directed spanning forest is almost surely a tree
• Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networks
• Semi-Infinite Paths of the Two-Dimensional Radial Spanning Tree
• Sublinearity of the number of semi-infinite branches for geometric random trees
• Moderate deviations for shortest-path lengths on random segment processes
• Asymptotics for first-passage times on Delaunay triangulations
• Stretch factor in a planar Poisson-Delaunay triangulation with a large intensity

This page was built for publication: Coalescence of Euclidean geodesics on the Poisson-Delaunay triangulation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708982)