On Some fundamental aspects of Polyominoes on Random Voronoi Tilings

Consider a Voronoi tiling of the Euclidean space based on a realization of a inhomogeneous Poisson random set. A Voronoi polyomino is a finite and connected union of Voronoi tiles. In this paper we provide tail bounds for the number of boxes that are intersected by a Voronoi polyomino, and vice-versa. These results will be crucial to analyze self-avoiding paths, greedy polyominoes and first-passage percolation models on Voronoi tilings and on the dual graph, named the Delaunay triangulation.