Complexity of Tiling a Polygon with Trominoes or Bars
Complexity of Tiling a Polygon with Trominoes or Bars
复制标题
DOI：
10.1007/s00454-017-9884-9
复制
发表时间：
2017-10-01
影响因子：
0.8
通讯作者：
Uehara, Ryuhei
中科院分区：
文献类型：
--
作者：
Horiyama, Takashi;Ito, Takehiro;Uehara, Ryuhei
我们研究了多联骨牌拼图的计算难度，其中多联骨牌是直角多边形（即，通过沿边缘连接单位正方形而形成的多边形）。在平铺问题中，我们给定一个直角多边形 P 和一组多骨骨牌 S，并询问是否可以使用 S 中多骨骨牌的平移副本来覆盖 P，而不会出现任何重叠。在本文中，我们重点关注作为多骨骨牌的 trominoes 和 bar；多米诺骨牌是由三个单位正方形组成的多骨骨牌，而条形则是高度为一或宽度为一的矩形。请注意，特罗米诺骨牌本质上有两种形状，即 I 形（即条形）和 L 形。我们考虑仅限于仅 L 形支架、仅 I 形支架、L 形和 I 形支架或仅两个条时的平铺问题。在本文中，我们证明即使对于这种受限的多联骨牌集合，平铺问题仍然是 NP 完全的。所有归约都经过精心设计，以便我们还可以分别证明计数和另一个解决方案问题变体的 # P 完整性和 ASP 完整性。我们的结果回答了 Moore 和 Robson (Discrete Comput Geom 26:573-590, 2001) 以及 Pak 和 Yang (J Comb Theory 120:1804-1816, 2013) 提出的两个开放性问题。
We study the computational hardness of the tiling puzzle with polyominoes, where a polyomino is a right-angled polygon (i.e., a polygon made by connecting unit squares along their edges). In the tiling problem, we are given a right-angled polygon P and a set S of polyominoes, and asked whether P can be covered without any overlap using translated copies of polyominoes in S. In this paper, we focus on trominoes and bars as polyominoes; a tromino is a polyomino consisting of three unit squares, and a bar is a rectangle of either height one or width one. Notice that there are essentially two shapes of trominoes, that is, I-shape (i.e., a bar) and L-shape. We consider the tiling problem when restricted to only L-shape trominoes, only I-shape trominoes, both L-shape and I-shape trominoes, or only two bars. In this paper, we prove that the tiling problem remains NP-complete even for such restricted sets of polyominoes. All reductions are carefully designed so that we can also prove the # P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively. Our results answer two open questions proposed by Moore and Robson (Discrete Comput Geom 26:573-590, 2001) and Pak and Yang (J Comb Theory 120:1804-1816, 2013).