Complexity of tile rotation problems

Eric Goles, Iván Rapaport

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


In this paper we introduce tile rotation problems. The instances (or initial configurations) are tile assignments on a (n x n) lattice board, and the question to be answered is the following: does there exist any configuration obtained from the initial one by tile rotations only whose cost is less than a given bound? (notice that a zero-cost configuration corresponds to a perfect tiling). We prove here the NP-completeness for both the zero-cost problem (for a particular set of 5 tiles) and the minimization problem (for a particular set of 2 tiles). Finally, by showing the polynomiality of some subproblems, we establish complexity border results.

Original languageEnglish
Pages (from-to)129-159
Number of pages31
JournalTheoretical Computer Science
Issue number1-2
StatePublished - 30 Nov 1997
Externally publishedYes


Dive into the research topics of 'Complexity of tile rotation problems'. Together they form a unique fingerprint.

Cite this