First-passage percolation on the Voronoi tessellation and Delaunay triangulation. (English) Zbl 0760.05023

Random graphs ’87, Proc. 3rd Int. Semin., Poznań/Poland 1987, 341-359 (1990).
[For the entire collection see Zbl 0726.00010.]
Our principal result gives necessary and sufficient conditions for almost sure convergence of the normalized first-passage time process:
Theorem. For both the Voronoi tessellation and the Delaunay triangulation, there exists a constant \(\mu(F)<+\infty\) such that \(\lim_{x\to\infty}{t(0,x)\over x}=\mu(F)\) exists a.s. and in mean if and only if \(\int^ \infty_ 0[1-F(t)]^ 3dt<+\infty\).
The proof of the Theorem is presented in section 2. Open problems involving percolation models on the Voronoi tesselation and Delaunay triangulation are discussed in section 3.


05B45 Combinatorial aspects of tessellation and tiling problems
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82B43 Percolation


Zbl 0726.00010