Institute of Mathematics
Opole University
and
Institute of Computer Science
University of Wrocław
Przesmyckiego 20
51-151 Wrocław
Poland
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).
Published in Proceedings of 28th Conference on Current Trends in Theory
and Practice of Informatics (SOFSEM), Piestany, Slovakia, November 24 - December 1, 2001,
Lecture Notes in Computer Science,
vol. 2234, Springer-Verlag 2001, pp. 253-260
and also in journal
Computing and Informatics, Vol. 21 (3), 2002, pp. 241-249.
*Supported by KBN grant 8 T11C 043 19
Maciej.Gebala@pwr.edu.pl