The reconstruction of polyominoes from approximately orthogonal projections

Authors

  • Maciej Gębala

Abstract

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

Downloads

Download data is not yet available.

Published

2012-02-21

How to Cite

Gębala, M. (2012). The reconstruction of polyominoes from approximately orthogonal projections. Computing and Informatics, 21(3), 241–249. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/494