DMTCS Proceedings, Discrete Models for Complex Systems, DMCS'03

Font Size:  Small  Medium  Large

Tiling a Rectangle with Polyominoes

Olivier Bodini


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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional