The Reconstruction of Convex Polyominoes from Horizontal and Vertical Projections
Maciej Gȩbala · 1998
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 atmost O(min(m;n)² \\Delta mn log mn) for a matrix that has m \\Theta n cells. In this paper we provide just a sketch of the algorithm.