Hard tiling problems with simple tiles

被引：92

作者：

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

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 2001年 / 26卷 / 04期

关键词：

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 [J].

BEAUQUIER, D ;

NIVAT, M ;

REMILA, E ;

ROBSON, M .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 1995, 5 (01) :1-25

[3] ON TRANSLATING ONE POLYOMINO TO TILE THE PLANE [J].

BEAUQUIER, D ;

NIVAT, M .

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 [J].

Goles, E ;

Rapaport, I .

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 [J].

KASTELEYN, P .

PHYSICA, 1961, 27 (12) :1209-+

[10] Isohedral polyomino tiling of the plane [J].

Keating, K ;

Vince, A .

DISCRETE & COMPUTATIONAL GEOMETRY, 1999, 21 (04) :615-630

← 1 2 3 →