Moore, C.; Robson, J. M. Hard tiling problems with simple tiles. (English) Zbl 1021.68097 Discrete Comput. Geom. 26, No. 4, 573-590 (2001). Summary: It is well known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process we show that monotone 1-in-3 satisfiability is NP-complete for planar cubic graphs. In higher dimensions we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply connected regions on the four-dimensional hypercubic lattice. Cited in 1 ReviewCited in 61 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) Keywords:tilings; halting problem PDFBibTeX XMLCite \textit{C. Moore} and \textit{J. M. Robson}, Discrete Comput. Geom. 26, No. 4, 573--590 (2001; Zbl 1021.68097) Full Text: DOI arXiv