Tiling simply connected regions with rectangles

Igor Pak, Jed Yang

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

In 1995, Beauquier, Nivat, Rémila, and Robson showed that tiling of general regions with two bars is NP-complete, except for a few trivial special cases. In a different direction, in 2005, 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 106rectangles 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.

Original languageEnglish (US)
Pages (from-to)1804-1816
Number of pages13
JournalJournal of Combinatorial Theory. Series A
Volume120
Issue number7
DOIs
StatePublished - Sep 2013

Bibliographical note

Funding Information:
We are grateful to Alex Fink, Jeff Lagarias, Leonid Levin, Cris Moore, Günter Rote, and Damien Woods for helpful conversations at various stages of this project. We also thank the anonymous referees for attentive reading of the paper and useful comments. The first author is partially supported by the NSF and BSF grants. The second author is supported by the NSF under Grant No. DGE-0707424 .

Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

Keywords

  • #P-completeness
  • NP-completeness
  • Rectangles
  • Tiling

Fingerprint Dive into the research topics of 'Tiling simply connected regions with rectangles'. Together they form a unique fingerprint.

Cite this