Olivier Bodini - Tiling a Rectangle with Polyominoes

dmtcs:2313 - Discrete Mathematics & Theoretical Computer Science, January 1, 2003, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03) - https://doi.org/10.46298/dmtcs.2313
Tiling a Rectangle with PolyominoesConference paper

Authors: Olivier Bodini ORCID1

A polycube in dimension d is a finite union of unit d-cubes whose vertices are on knots of the lattice Zd. 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.


Volume: DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03)
Section: Proceedings
Published on: January 1, 2003
Imported on: November 21, 2016
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]

3 Documents citing this article

Consultation statistics

This page has been seen 415 times.
This article's PDF has been downloaded 308 times.