Tiling a Rectangle with Polyominoes

Abstract

A polycube in dimension $d$ is a finite union of unit $d$-cubes whose vertices are on knots of the lattice $\mathbb{Z}^d$. We show that, for each family of polycubes $E$, there exists a finite set $F$ of bricks (parallelepiped rectangles) such that the bricks which can be tiled by $E$ are exactly the bricks which can be tiled by $F$. Consequently, if we know the set $F$, then we have an algorithm to decide in polynomial time if a brick is tilable or not by the tiles of $E$.

Keywords

• tiling
• polyomino
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [nlin.nlin-cg] nonlinear sciences [physics]/cellular automata and lattice gases [nlin.cg]