Multifold Tiles of Polyominoes and Convex Lattice Polygons

Discrete and Computational Geometry, Graphs, and Games

Abstract

A planar shape $S$ is a $k$-fold tile if there is an indexed family $\mathcal{T}$ of planar shapes congruent to $S$ that is a $k$-fold tiling: any point in $\mathbb{R}^2$ that is not on the boundary of any shape in $\mathcal{T}$ is covered by exactly $k$ shapes in $\mathcal{T}$. Since a 1-fold tile is clearly a $k$-fold tile for any positive integer $k$, the subjects of our research are \emph{nontrivial $k$-fold tiles}, that is, plane shapes with property "not a 1-fold tile, but a $k(\geq 2)$-fold tile." In this paper, we prove some interesting properties about nontrivial $k$-fold tiles. First, we show that, for any integer $k \geq 2$, there exists a polyomino with property "not an $h$-fold tile for any positive integer $h<k$, but a $k$-fold tile." We also find, for any integer $k \geq 2$, polyominoes with the minimum number of cells among ones that are nontrivial $k$-fold tiles. Next, we prove that, for any integer $k=5$ or $k \geq 7$, there exists a convex unit-lattice polygon that is a nontrivial $k$-fold tile whose area is $k$, and for $k=2$ and $k=3$, no such convex unit-lattice polygon exists.