Hard tiling problems with simple tiles

被引:87
作者
Moore, C [1 ]
Robson, JM
机构
[1] Univ New Mexico, Dept Comp Sci, Albuquerque, NM 87131 USA
[2] Univ New Mexico, Dept Phys & Astron, Albuquerque, NM 87131 USA
[3] Santa Fe Inst, Santa Fe, NM 87501 USA
[4] Univ Bordeaux 1, LaBRI, F-33405 Talence, France
关键词
D O I
10.1007/s00454-001-0047-6
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
It is well known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process we show that Monotone 1-in-3 Satisfiability is NP-complete for planar cubic graphs. In higher dimensions we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply connected regions on the four-dimensional hypercubic lattice.
引用
收藏
页码:573 / 590
页数:18
相关论文
共 21 条
  • [1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
  • [2] TILING FIGURES OF THE PLANE WITH 2 BARS
    BEAUQUIER, D
    NIVAT, M
    REMILA, E
    ROBSON, M
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1995, 5 (01): : 1 - 25
  • [3] ON TRANSLATING ONE POLYOMINO TO TILE THE PLANE
    BEAUQUIER, D
    NIVAT, M
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1991, 6 (06) : 575 - 592
  • [4] Berger R., 1966, MEM AM MATH SOC, V66
  • [5] Di Battista G., 1999, GRAPH DRAWING
  • [6] Goldschlager L. M., 1977, SIGACT News, V9, P25, DOI 10.1145/1008354.1008356
  • [7] Tiling allowing rotations only
    Goles, E
    Rapaport, I
    [J]. THEORETICAL COMPUTER SCIENCE, 1999, 218 (02) : 285 - 295
  • [8] Golomb S.W., 1994, Polyominoes, Puzzles, Patterns, Problems, and Packagings, Vsecond
  • [9] STATISTICS OF DIMERS ON A LATTICE .1. NUMBER OF DIMER ARRANGEMENTS ON A QUADRATIC LATTICE
    KASTELEYN, P
    [J]. PHYSICA, 1961, 27 (12): : 1209 - +
  • [10] Isohedral polyomino tiling of the plane
    Keating, K
    Vince, A
    [J]. DISCRETE & COMPUTATIONAL GEOMETRY, 1999, 21 (04) : 615 - 630