# 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 :
Type de document :
Communication dans un congrès
Michel Morvan and Éric Rémila. Discrete Models for Complex Systems, DMCS'03, 2003, Lyon, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03), pp.81-88, 2003, DMTCS Proceedings
Domaine :

Littérature citée [9 références]

https://hal.inria.fr/hal-01183321
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 10:14:52
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:35:19

### Fichier

dmAB0107.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01183321, version 1

### Citation

Olivier Bodini. Tiling a Rectangle with Polyominoes. Michel Morvan and Éric Rémila. Discrete Models for Complex Systems, DMCS'03, 2003, Lyon, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03), pp.81-88, 2003, DMTCS Proceedings. 〈hal-01183321〉

### Métriques

Consultations de la notice

## 168

Téléchargements de fichiers