Tiling simply connected regions with rectangles

2013/05/13 by Igor Pak, Pak, Igor, Jed Yang +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #52C20 (Primary) 05B45 #68Q17 (Secondary) #Cellular Automata and Applications #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.1305.2796

openalex publication_date 2013/05/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In [BNRR], it was shown that tiling of general regions with two rectangles is NP-complete, except for a few trivial special cases. In a different direction, Rémila showed that for simply connected regions by two rectangles, the tileability can be solved in quadratic time (in the area). We prove that there is a finite set of at most 10⁶ rectangles for which the tileability problem of simply connected regions is NP-complete, closing the gap between positive and negative results in the field. We also prove that counting such rectangular tilings is #P-complete, a first result of this kind.

Citations

• An introduction to the dimer model
• Clustering to minimize the maximum intercluster distance
• The undecidability of the domino problem
• The Complexity of Enumeration and Reliability Problems
• The complexity of generalized domino tilings

Cited by

• Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping

Related

• NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
• Hard Tiling Problems with Simple Tiles
• Rectangular tileability and complementary tileability are undecidable
• Minimizing the Number of Tiles in a Tiled Rectangle
• When Can You Tile an Integer Rectangle with Integer Squares?