On Subtilings of Polyomino Tilings

Abstract

We consider a problem concerning tilings of rectangular regions by a finite library of polyominoes. We specifically look at rectangular regions of dimension $n\times m$ and ask whether or not a tiling of this region can be rearranged so that tiling of the $n\times m$ rectangle can be realized as a tiling of an $n\times m^{\prime }$ rectangle and an $n\times m"$ rectangle, $m=m^{\prime }+m"$. We call this a subtiling. We show that the associated decision problem is $\mathsf{NP}$-complete when restricted to rectangular polyominoes. We also show that for certain finite libraries of polyominoes, if $m$ is sufficiently large, a subtiling always exists and give bounds.

References in corpus (2)

• A Complete Set of Invariants for LU-Equivalence of Density Operators
• The Invariant Ring Of m Matrices Under The Adjoint Action By a Product Of General Linear Groups

Cited by in corpus (1)

• A Complete Set of Invariants for LU-Equivalence of Density Operators