×

Hard tiling problems with simple tiles. (English) Zbl 1021.68097

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.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI arXiv