论文标题
在有限的王瓷砖上
On bounded Wang tilings
论文作者
论文摘要
Wang Tiles通过可编程匹配规则避免了瓷砖分布的周期性，从而实现有效的模式压缩。然而，王瓦林斯的大多数研究都认为无限平面铺平了瓷砖。由材料工程中新兴应用的促进，我们考虑了瓷砖问题的有限版本，并提供了四个整数编程公式，以构建有效或近乎瓦利德的王朝瓷砖：决策，最大矩形瓷砖，最大覆盖层，最大掩盖和最大的邻接约束满意度。为了促进对所得瓷砖的更好控制，我们使用基于瓷砖的，基于颜色的，包装和可变大小的周期性约束扩展了这些程序。此外，我们根据有向无环图中的最短路径搜索引入了一种有效的启发式算法，以实现最大覆盖变体，并得出简单的修改，以提供任意瓷砖集的$ 1/2 $近似保证，并提供$ 2/3 $的$ 2/3 $保证，用于使用环形传输者的瓷砖设置。最后，我们基于整数编程公式的性能和启发式算法的性能，表明启发式方法在很短的时间内提供了非常有竞争力的输出。作为副产品，我们在两个众所周知的Aperiodic瓷砖集中揭示了错误：Knuth Tile套件在双向无限的瓷砖中包含一个无法使用的瓷砖，而Lagae Corner Tile tile套件也不是Aperiodic。
Wang tiles enable efficient pattern compression while avoiding the periodicity in tile distribution via programmable matching rules. However, most research in Wang tilings has considered tiling the infinite plane. Motivated by emerging applications in materials engineering, we consider the bounded version of the tiling problem and offer four integer programming formulations to construct valid or nearly-valid Wang tilings: a decision, maximum-rectangular tiling, maximum cover, and maximum adjacency constraint satisfaction formulations. To facilitate a finer control over the resulting tilings, we extend these programs with tile-based, color-based, packing, and variable-sized periodic constraints. Furthermore, we introduce an efficient heuristic algorithm for the maximum-cover variant based on the shortest path search in directed acyclic graphs and derive simple modifications to provide a $1/2$ approximation guarantee for arbitrary tile sets, and a $2/3$ guarantee for tile sets with cyclic transducers. Finally, we benchmark the performance of the integer programming formulations and of the heuristic algorithms showing that the heuristics provides very competitive outputs in a fraction of time. As a by-product, we reveal errors in two well-known aperiodic tile sets: the Knuth tile set contains a tile unusable in two-way infinite tilings, and the Lagae corner tile set is not aperiodic.
