Tiling Figures of the Plane with Two Bars
Tiling Figures of the Plane with Two Bars
复制标题
DOI：
10.1016/0925-7721(94)00015-n
复制
发表时间：
1995-03
期刊：
影响因子：
--
通讯作者：
D. Beauquier;M. Nivat;É. Rémila;M. Robson
中科院分区：
文献类型：
--
作者：
D. Beauquier;M. Nivat;É. Rémila;M. Robson
给出两个“条”，一个水平的，一个垂直的(长度至少有两个)，我们感兴趣的是下面的判定问题：是画在可用这些条旋转的平面网格上的有限图形。事实证明，如果其中一根棒子至少有三个长度，那么问题就是NP完全的。如果条形是多米诺骨牌，那么问题出在P中，甚至对于某些类别的图形而言，甚至是线性的(图形的大小)。给出了一个一般的条形对，我们给出了两个结果：(1)有限个无孔图形存在唯一拼贴的必要条件；(2)一个线性算法(在图形的大小内)决定是否存在唯一的拼贴，如果存在，则计算此唯一拼贴。最后，给定一个图形的平铺(不一定是有限的)，当且仅当不存在覆盖“规范”矩形的子平铺时，该平铺才是该图形的唯一平铺。
Given two “bars”, a horizontal one, and a vertical one (both of length at least two), we are interested in the following decision problem: is a finite figure drawn on a plane grid tilable with these bars. It turns out that if one of the bars has length at least three, the problem is NP-complete. If bars are dominoes, the problem is in P, and even linear (in the size of the figure) for certain classes of figures. Given a general pair of bars, we give two results: (1) a necessary condition to have a unique tiling for finite figures without holes, (2) a linear algorithm (in the size of the figure) deciding whether a unique tiling exists, and computing this one if it does exist. Finally, given a tiling of a figure (not necessarily finite), this tiling is the unique one for the figure if and only if there exists no subtiling covering a “canonical” rectangle.