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
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
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

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

Collections

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〉

Partager

Métriques

Consultations de la notice

131

Téléchargements de fichiers

141