Reconstruction of domino tiling from its two orthogonal projections

被引：11

作者：

Picouleau, C ^{[1
]}

机构：

[1] Conservatoire Natl Arts & Metiers, Lab CEDRIC, F-75003 Paris, France

来源：

THEORETICAL COMPUTER SCIENCE | 2001年 / 255卷 / 1-2期

关键词：

domino tiling; reconstruction problem; polynomial-time algorithm; NP-completeness;

D O I：

10.1016/S0304-3975(99)00312-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We are interested in the reconstruction of a domino tiling of a rectangle from its two orthogonal projections. We give polynomial algorithms for some subproblems when all the dominoes are of the same type and prove NP-completeness results when there are three types of dominoes. When two types of dominoes are allowed. we give a polynomial-time transformation from a well-known open problem. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：437 / 447

页数：11

共 11 条

[1] Ahuja R.K., 1993, NETWORK FLOWS THEORY
[2] [Anonymous], 1991, COMPUTERS INTRACTABI
[3] Reconstructing convex polyominoes from horizontal and vertical projections
Barcucci, E
DelLungo, A
Nivat, M
Pinzani, R
[J]. THEORETICAL COMPUTER SCIENCE, 1996, 155 (02) : 321 - 347
[4] BARCUCCI E, 1995, 1595 U FIR DIP SIST
[5] Berge C., 1983, Graphes
[6] CHROBAK M, 1998, 98012 ICSI
[7] The number of convex polyominoes reconstructible from their orthogonal projections
DelLungo, A
Nivat, M
Pinzani, R
[J]. DISCRETE MATHEMATICS, 1996, 157 (1-3) : 65 - 78
[8] POLYOMINOES DEFINED BY 2 VECTORS
DELLUNGO, A
[J]. THEORETICAL COMPUTER SCIENCE, 1994, 127 (01) : 187 - 198
[9] GARDNER H, 1999, IN PRESS THEORET COM
[10] Discrete tomography: Determination of finite sets by X-rays
Gardner, RJ
Gritzmann, P
[J]. TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY, 1997, 349 (06) : 2271 - 2295

← 1 2 →