E. Barcucci et al., RECONSTRUCTING CONVEX POLYOMINOES FROM HORIZONTAL AND VERTICAL PROJECTIONS, Theoretical computer science, 155(2), 1996, pp. 321-347
Citations number
32
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
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.