Tiling simply connected regions with rectangles

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:120

Article

Pak, Igor¹  Yang, Jed¹ 

[1] Univ Calif Los Angeles, Dept Math, Los Angeles, CA 90095 USA

关键词: Tiling;    Rectangles;    NP-completeness;    #P-completeness;   

DOI  :  10.1016/j.jcta.2013.06.008

来源: Elsevier

【 摘 要 】

In 1995, Beauquier, Nivat, Remila, 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, Remila 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. (C) 2013 Elsevier Inc. All rights reserved.

【 授权许可】

Free