Complexity of tile rotation problems

Goles, E.; Rapaport, I

Keywords: rotation, polynomials, theorem, complexity, problems, problem, solving, Computational, proving, Tile

Abstract

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.

Más información

Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 188
Número: 1-2
Editorial: ELSEVIER SCIENCE BV
Fecha de publicación: 1997
Página de inicio: 129
Página final: 159
URL: http://www.scopus.com/inward/record.url?eid=2-s2.0-0031270477&partnerID=q2rCbXpz