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

Vahidi-Asl, Mohammed Q.; Wierman, John C.

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.

MSC:

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

Keywords:

first-passage time process; Voronoi tessellation; Delaunay triangulation; percolation models

Citations:

Zbl 0726.00010