Markov paths on the Poisson-Delaunay graph with applications to routeing in mobile networks

Consider the Delaunay graph and the Voronoi tessellation constructed with r espect to a Poisson point process. The sequence of nuclei of the Voronoi ce lls that are crossed by a line defines a path on the Delaunay graph. We sho w that the evolution of this path is governed by a Markov chain. We study t he ergodic properties of the chain and find its stationary distribution. As a corollary, we obtain the ratio of the mean path length to the Euclidean distance between the end points, and hence a bound for the mean asymptotic length of the shortest path. We apply these results to define a family of simple incremental algorithms for constructing short paths on the Delaunay graph and discuss potential ap plications to routeing in mobile communication networks.