Moderate deviations for shortest-path lengths on random segment processes

¹ Weierstrass Institute for Applied Analysis and Stochastics, 10117 Berlin, Germany.
christian.hirsch@wias-berlin.de
² Institute of Stochastics, Ulm University, 89069 Ulm, Germany.

Received: 6 May 2015
Accepted: 4 May 2016

Abstract

We consider first-passage percolation on segment processes and provide concentration results concerning moderate deviations of shortest-path lengths from a linear function in the distance of their endpoints. The proofs are based on a martingale technique developed by [H. Kesten, Ann. Appl. Probab. 3 (1993) 296–338.] for an analogous problem on the lattice. Our results are applicable to graph models from stochastic geometry. For example, they imply that the time constant in Poisson−Voronoi and Poisson−Delaunay tessellations is strictly greater than 1. Furthermore, applying the framework of Howard and Newman, our results can be used to study the geometry of geodesics in planar shortest-path trees.