Polyomino convolutions and tiling problems (Q5947369)
From MaRDI portal
scientific article; zbMATH DE number 1660992
Language | Label | Description | Also known as |
---|---|---|---|
English | Polyomino convolutions and tiling problems |
scientific article; zbMATH DE number 1660992 |
Statements
Polyomino convolutions and tiling problems (English)
0 references
30 September 2003
0 references
The author considers tilings of the plane by copies of a given polyomino, with rotations and translations allowed, and gives a new criterion to show that a given polyomino does not allow a tiling. Usually it is quite difficult to decide whether some given polyomino tiles the plane; in fact there are several results showing algorithmic hardness of deciding if a set of polyominoes allows a tiling of the plane, e.g. \textit{R. M. Robinson} [Invent. Math. 12, 177--209 (1971; Zbl 0199.30802)], so one cannot expect any simple criterion answering all cases. Therefore any new criterion is interesting. The author's criterion is based on a convolution operation for polyominoes, it is a sufficient criterion for the nonexistence of a tiling, and the author shows that it answers some cases which cannot be answered by previous coloring-type arguments.
0 references
tiling by polyominoes
0 references
impossibility of tiling
0 references