# 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 :
Document type :
Conference papers
Domain :

Cited literature [9 references]

https://hal.inria.fr/hal-01183321
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 10:14:52 AM
Last modification on : Thursday, May 24, 2018 - 3:59:21 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:35:19 AM

### File

dmAB0107.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01183321, version 1

### Citation

Olivier Bodini. Tiling a Rectangle with Polyominoes. Discrete Models for Complex Systems, DMCS'03, 2003, Lyon, France. pp.81-88. ⟨hal-01183321⟩

Record views