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 -