6533b872fe1ef96bd12d37df

RESEARCH PRODUCT

The Reconstruction of Polyominoes from Approximately Orthogonal Projections

Maciej Gebala

subject

Mathematics::CombinatoricsPolyominoComputational complexity theoryComputer scienceOrthographic projectionRegular polygonVector projectionComputer Science::Computational GeometryCombinatoricsProjection (mathematics)Computer Science::Discrete MathematicsTomographyAlgorithmTime complexityComputer Science::Formal Languages and Automata TheoryImage compression

description

The reconstruction of discrete two-dimensional pictures from their projection is one of the central problems in the areas of medical diagnostics, computer-aided tomography, pattern recognition, image processing, and data compression. In this note, we determine the computational complexity of the problem of reconstruction of polyominoes from their approximately orthogonal projections. We will prove that it is NP-complete if we reconstruct polyominoes, horizontal convex polyominoes and vertical convex polyominoes. Moreover we will give the polynomial algorithm for the reconstruction of hv-convex polyominoes that has time complexity O(m3n3).

yearjournalcountryeditionlanguage
2001-01-01
https://doi.org/10.1007/3-540-45627-9_22