@article{EJP1788,
author = {Raphaël Rossignol and Leandro Pimentel},
title = {Greedy polyominoes and first-passage times on random Voronoi tilings},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {17},
year = {2012},
keywords = {Random Voronoi tiling; Delaunay graph; First passage percolation; connective constant; greedy animal; random walk},
abstract = {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.},
pages = {no. 12, 1-31},
issn = {1083-6489},
doi = {10.1214/EJP.v17-1788},
url = {http://ejp.ejpecp.org/article/view/1788}}