TY - JOUR

T1 - Tiling allowing rotations only

AU - Goles, Eric

AU - Rapaport, Ivan

N1 - Funding Information:
* Corresponding author. E-mail: irapapor@dim.uchile.cl. ’ This work was partially supported by FONDAP on Applied Mathematics

PY - 1999/5/26

Y1 - 1999/5/26

N2 - We define a "rotating board" as a finite square with one tile fixed in each cell. These fixed tiles can only be rotated and, in addition, they belong to a particular set of four tiles constructed with two colors. In this paper we show that any set of tiles script T sign may be coded in linear time into a "rotating board" B in the following sense: i. There exists an injection from the colors of the tiles of script T sign into the set of border conditions of the board B. ii. There is a one-to-one relation between the set script T sign and the set of tilings of B (obtained by rotating its tiles) satisfying that each t ∈ script T sign is associated to a tiling Bθ in such a way that the (north, south, east and west) colors of t are related to the (north, south, east and west) border conditions of Bθ by the injection of i. The existence of this coding means that we can efficiently transform an arbitrary degrees of freedom tiling problem (in which to each cell is assigned an arbitrary set of admissible tiles) into a restricted four degrees of freedom problem (in which the tiles, fixed in each cell, can only be rotated). Considering the classical tiling results, we conclude the NP-completeness (resp. undecidability) of the natural bounded (resp. unbounded) version of the rotation tiling problem.

AB - We define a "rotating board" as a finite square with one tile fixed in each cell. These fixed tiles can only be rotated and, in addition, they belong to a particular set of four tiles constructed with two colors. In this paper we show that any set of tiles script T sign may be coded in linear time into a "rotating board" B in the following sense: i. There exists an injection from the colors of the tiles of script T sign into the set of border conditions of the board B. ii. There is a one-to-one relation between the set script T sign and the set of tilings of B (obtained by rotating its tiles) satisfying that each t ∈ script T sign is associated to a tiling Bθ in such a way that the (north, south, east and west) colors of t are related to the (north, south, east and west) border conditions of Bθ by the injection of i. The existence of this coding means that we can efficiently transform an arbitrary degrees of freedom tiling problem (in which to each cell is assigned an arbitrary set of admissible tiles) into a restricted four degrees of freedom problem (in which the tiles, fixed in each cell, can only be rotated). Considering the classical tiling results, we conclude the NP-completeness (resp. undecidability) of the natural bounded (resp. unbounded) version of the rotation tiling problem.

UR - http://www.scopus.com/inward/record.url?scp=0038850144&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(98)00327-2

DO - 10.1016/S0304-3975(98)00327-2

M3 - Article

AN - SCOPUS:0038850144

VL - 218

SP - 285

EP - 295

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 2

ER -