The Reconstruction of Convex Polyominoes from Horizontal and Vertical Projections

Maciej Gębala

Institute of Computer Science
University of Wrocław
Przesmyckiego 20
51-151 Wrocław
Poland


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(m2, n2) 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.

Valid XHTML 1.1! Valid CSS!

Maciej.Gebala@pwr.edu.pl