The Reconstruction of Convex Polyominoes from Horizontal and Vertical Projections

Abstract

The problem of reconstructing a discrete set from its horizontal and vertical projections is of primary importance in many different problems for example pattern recognition, image processing and data compression.

We give a new algorithm which provides a reconstruction of convex polyominoes from horizontal and vertical projections. It costs at most O(min(m², n²) mn log mn) for a matrix that has m x n cells. In this paper we provide just a sketch of the algorithm.

Published in Proceedings of 25th Conference on Current Trends in Theory and Practice of Informatics (SOFSEM), Jasna, Slovakia, November 21-27, 1998, Lecture Notes in Computer Science, vol. 1521, Springer-Verlag 1998, pp. 350-359.

Conference paper

Conference presentation.