The Reconstruction of Convex Polyominoes from Horizontal and Vertical Projections
by Maciej Gebala
Abstract:
The problem of reconstructing a discrete set from its horizontal and vertical projections (RSP) 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(n^2 m^2 \log(mn))$. In this paper we provide just a sketch of the algorithm.