Reconstruction of domino tiling from its two orthogonal projections
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.
domino tiling np-completeness reconstruction problem polynomial-time algorithm