Reconstruction of domino tiling from its two orthogonal projections

DOI10.1016/S0304-3975(99)00312-6zbMath0973.68245MaRDI QIDQ5941081

Christophe Picouleau

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

NP-completenesspolynomial-time algorithmdomino tilingreconstruction problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (n) dimensions (aspects of discrete geometry) (52C22)

Related Items

The NP-completeness of a tomographical problem on bicolored domino tilings, Tiling with bars under tomographic constraints., On tiling under tomographic constraints., A MIP flow model for crop-rotation planning in a context of forest sustainable development, Reconstruction of binary matrices under fixed size neighborhood constraints, Tile-packing tomography is \(\mathbb{NP}\)-hard, Complexity results for the horizontal bar packing problem, Approximating hv-Convex Binary Matrices and Images from Discrete Projections, The reconstruction of a subclass of domino tilings from two projections, Reconstruction of low degree domino tilings, Reconstruction of binary matrices under adjacency constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing convex polyominoes from horizontal and vertical projections
• Polyominoes defined by two vectors
• The number of convex polyominoes reconstructible from their orthogonal projections
• Discrete tomography: Determination of finite sets by X-rays
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms