• 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