Title of article
Tiling simply connected regions with rectangles
Author/Authors
Pak، نويسنده , , Igor and Yang، نويسنده , , Jed، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2013
Pages
13
From page
1804
To page
1816
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 106 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.
Keywords
Tiling , NP-Completeness , Rectangles , #P-completeness
Journal title
Journal of Combinatorial Theory Series A
Serial Year
2013
Journal title
Journal of Combinatorial Theory Series A
Record number
1531945
Link To Document