Greedy polyominoes and first-passage times on random Voronoi tilings

DOI10.1214/EJP.V17-1788zbMATH Open1246.60120arXiv0811.0308OpenAlexW2032579070MaRDI QIDQ428615FDOQ428615

Authors: Raphaël Rossignol, Leandro P. R. Pimentel 

Publication date: 22 June 2012

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Abstract: Let N be distributed as a Poisson random set on R^d with intensity comparable to the Lebesgue measure. Consider the Voronoi tiling of R^d, (C_v)_{vin N}, where C_v is composed by points x in R^d that are closer to v than to any other v' in N. A polyomino P of size n is a connected union (in the usual R^d topological sense) of n tiles, and we denote by Pi_n the collection of all polyominos 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 the tail behavior of the maximal weight among polyominoes in Pi_n for some functionals F, mainly when F(C_v) is the number of faces of 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 work available at URL: https://arxiv.org/abs/0811.0308

Recommendations

• On some fundamental aspects of polyominoes on random Voronoi tilings
• Estimates for distributions of the Voronoi polygon's geometric characteristics
• scientific article; zbMATH DE number 17688
• Percolation in Voronoi tilings
• Euclidean models of first-passage percolation

zbMATH Keywords

random walkfirst passage percolationDelaunay graphconnective constantgreedy animalrandom Voronoi tiling

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Cited In (4)

• Transversal fluctuations for a first passage percolation model
• On some fundamental aspects of polyominoes on random Voronoi tilings
• Recurrence or transience of random walks on random graphs generated by point processes in \(\mathbb{R}^d\)
• Stochastic geometry: Boolean model and random geometric graphs

This page was built for publication: Greedy polyominoes and first-passage times on random Voronoi tilings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q428615)