RECONSTRUCTING CONVEX POLYOMINOES FROM HORIZONTAL AND VERTICAL PROJECTIONS

Reconstructing discrete bidimensional sets from their projections is i nvolved in many different problems of computer-aided tomography, patte rn 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 project ions (H, V). We develop an algorithm that starts out from (H, V) and r econstructs set S, when S is a convex polyomino, in polynomial time. A t the same time, we show that determining the existence of a row-conve x (column-convex) polyomino or set with connected rows (columns) havin g assigned orthogonal projections (H, V) is an NP-complete problem. Mo reover, 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 seque nces are unimodal.