Greedy polyominoes and first-passage times on random Voronoi tilings

Raphaël Rossignol (Université Joseph Fourier Grenoble 1)
Leandro P. R. Pimentel (Federal University of Rio de Janeiro, Brazil)


Let $\mathcal{N}$ be distributed as a Poisson random set on $\mathbb{R}^d$, $d\geq 2$, with intensity comparable to the Lebesgue measure. Consider the Voronoi tiling of $\mathbb{R}^d$, $\{C_v\}_{v\in \mathcal{N}}$, where $C_v$ is composed of points $\mathbf{x}\in\mathbb{R}^d$ that are closer to $v\in\mathcal{N}$ than to any other $v'\in\mathcal{N}$.  A polyomino $\mathcal{P}$ of size $n$ is a connected union (in the usual $\mathbb{R}^d$ topological sense) of $n$ tiles, and we denote by $\Pi_n$ the collection of all polyominos $\mathcal{P}$ of size $n$ containing the origin. Assume that the weight of a Voronoi tile $C_v$ is given by $F(C_v)$, where $F$ is a nonnegative functional on Voronoi tiles. In this paper we investigate for some functionals $F$, mainly when $F(C_v)$ is a polynomial function of the number of faces of $C_v$,  the tail behavior of the maximal weight among polyominoes in $\Pi_n$: $F_n=F_n(\mathcal{N}):=\max_{\mathcal{P}\in\Pi_n} \sum_{v\in \mathcal{P}} F(C_v)$. Next we apply our results to study self-avoiding paths, first-passage percolation models and the stabbing number on the dual graph, named the Delaunay triangulation. As the main application we show that first passage percolation has at most linear variance.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-31

Publication Date: February 1, 2012

DOI: 10.1214/EJP.v17-1788


  • Addario-Berry, L. and Sarkar, A. (2005). The simple random walk on a random voronoi tiling. Available at URL.
  • Broutin, N. (2010). Private communication.
  • Calka, Pierre. Precise formulae for the distributions of the principal geometric characteristics of the typical cells of a two-dimensional Poisson-Voronoi tessellation and a Poisson line process. Adv. in Appl. Probab. 35 (2003), no. 3, 551--562. MR1990603
  • Cox, J. Theodore; Gandolfi, Alberto; Griffin, Philip S.; Kesten, Harry. Greedy lattice animals. I. Upper bounds. Ann. Appl. Probab. 3 (1993), no. 4, 1151--1169. MR1241039
  • Fontes, Luiz; Newman, Charles M. First passage percolation for random colorings of ${\bf Z}^ d$. Ann. Appl. Probab. 3 (1993), no. 3, 746--762. MR1233623
  • Grimmett, Geoffrey. Percolation. Springer-Verlag, New York, 1989. xii+296 pp. ISBN: 0-387-96843-1 MR0995460
  • Hammersley, J. M.; Welsh, D. J. A. First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. 1965 Proc. Internat. Res. Semin., Statist. Lab., Univ. California, Berkeley, Calif. pp. 61--110 Springer-Verlag, New York MR0198576
  • Houdré, C. and Privault, N. (2003). Surface measures and related functional inequalities on configuration spaces. Technical report, Université de La Rochelle. Prépublication 2003-04. Available at URL.
  • Howard, C. Douglas. Models of first-passage percolation. Probability on discrete structures, 125--173, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023652
  • Kesten, Harry. Aspects of first passage percolation. École d'été de probabilités de Saint-Flour, XIV—1984, 125--264, Lecture Notes in Math., 1180, Springer, Berlin, 1986. MR0876084
  • Kesten, Harry. On the speed of convergence in first-passage percolation. Ann. Appl. Probab. 3 (1993), no. 2, 296--338. MR1221154
  • Liggett, T. M.; Schonmann, R. H.; Stacey, A. M. Domination by product measures. Ann. Probab. 25 (1997), no. 1, 71--95. MR1428500
  • Pimentel, Leandro P. R. Asymptotics for first-passage times on Delaunay triangulations. Combin. Probab. Comput. 20 (2011), no. 3, 435--453. MR2784636
  • Pimentel, L. P. R. (2010). On some fundamental aspects of polyominoes on random Voronoi tilings. Accepted for publication by the Braz. J. of Probab. Stat.. Available at URL.
  • Vahidi-Asl, Mohammad Q.; Wierman, John C. First-passage percolation on the Voronoĭ tessellation and Delaunay triangulation. Random graphs '87 (Poznań, 1987), 341--359, Wiley, Chichester, 1990. MR1094141

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.