Reconstructing convex polyominoes from horizontal and vertical projections

AbstractReconstructing discrete bidimensional sets from their projections is involved in many different problems of computer-aided tomography, pattern recognition, image processing and data compression. In this paper, we examine the problem of reconstructing a discrete bidimensional set S satisfying some convexity conditions from its two orthogonal projections (H, V). We develop an algorithm that starts out from (H, V) and reconstructs set S, when S is a convex polyomino, in polynomial time. At the same time, we show that determining the existence of a row-convex (column-convex) polyomino or set with connected rows (columns) having assigned orthogonal projections (H, V) is an NP-complete problem. Moreover, by using the algorithm to reconstruct convex polyominoes from their two orthogonal projections we prove that the numerical matching with target sums problem can be solved in polynomial time if its sequences are unimodal