2016/02/18 by Jacob Turner, Turner, Jacob
Computer Science · Materials Science · Mathematics · #Cellular Automata and Applications #Combinatorics (math.CO) #Commutative Algebra (math.AC) #FOS: Mathematics #Mathematical Dynamics and Fractals #Quasicrystal Structures and Properties
paper · pdf · doi:10.48550/arxiv.1602.05784
openalex publication_date 2016/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a problem concerning tilings of rectangular regions by a finite library of polyominoes. We specifically look at rectangular regions of dimension n× m and ask whether or not a tiling of this region can be rearranged so that tiling of the n× m rectangle can be realized as a tiling of an n× m' rectangle and an n× m" rectangle, m=m'+m". We call this a subtiling. We show that the associated decision problem is 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.