Klarner Systems and Tiling Boxes with Polyominoes

Klarner Systems and Tiling Boxes with Polyominoes, by Michael Reid
Journal of Combinatorial Theory, Series A 111 (2005), no. 1, pp. 89-105.
[DOI] [Math Reviews] [Zentralblatt]
.dvi (78k) .ps (645k) .ps.gz (309k) .pdf (178k)
Given a protoset T, of n-dimensional polyominoes, what boxes can be tiled by T ? A fundamental result of Klarner and Göbel [2] asserts that the answer can always be described by giving a finite list of "prime" boxes. All other boxes that can be tiled can be deduced from this finite collection of prime boxes. Unfortunately, the proof in the original paper of Klarner and Göbel [2] has a gap for dimensions 3 and higher. Klarner repairs the proof in an unpublished technical report [1].
We give a new, simple and direct proof of this fundamental result, at the same time obtaining a slightly stronger statement. Moreover we show that there is no upper bound to the number of prime boxes of a protoset, even when restricting to a narrow class of protosets (namely, singleton protosets in 2 dimensions). In the last section, we determine the prime rectangles for some singleton protosets of small polyominoes, and show the variety of techniques that are used.
[1] David A. Klarner, A Finite Basis Theorem Revisited, Technical Report CS-TR-73-338, Stanford University, February 1973.
[2] D.A. Klarner and F. Göbel, Packing boxes with congruent figures, Indagationes Mathematicae 31 (1969) pp. 465-472. [Math Reviews]
Research page Home page E-mail
Updated January 6, 2008.