TY - JOUR
T1 - Complexity of tile rotation problems
AU - Goles, Eric
AU - Rapaport, Iván
N1 - Funding Information:
“Corresponding author. E-mail: [email protected], [email protected]. ‘This work was partially supported by projects FONDECYT 1940520 (E.G.-I.R.), ECUS (E.G.), and EC-CII*CT92-0046 (E.G.).
PY - 1997/11/30
Y1 - 1997/11/30
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0031270477&partnerID=8YFLogxK
U2 - 10.1016/S0304-3975(96)00291-5
DO - 10.1016/S0304-3975(96)00291-5
M3 - Article
AN - SCOPUS:0031270477
SN - 0304-3975
VL - 188
SP - 129
EP - 159
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-2
ER -