|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
The Reconstruction of Polyominoes from Approximately Orthogonal Projections
by Maciej Gebala
Abstract:
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 without any restriction, horizontal convex polyominoes and
vertical convex polyominoes. Moreover we will give the polynomial algorithm
for the reconstruction of hv-convex polyominoes that has $O(m^3 n^3)$
complexity.