Reconstruction of 4-and 8-connected convex discrete sets from row and column projections

In this paper we examine the problem of reconstructing a discrete two-dimen sional set from its two orthogonal projection (H, V) when the set satisfies some convexity conditions. We show that the algorithm of the paper [Int. J . Imaging Systems and Technol. 9 (1998) 69] is a good heuristic algorithm b ut it does not solve the problem for all (H, V) instances. We propose a mod ification of this algorithm solving the problem for all (H, V) instances, b y starting to build the "spine". The complexity of our reconstruction algor ithm is O(mn . log(mn) . min{m(2), n(2)}) in the worst case. However, accor ding to our experimental results, in 99% of the studied cases the algorithm is able to reconstruct a solution without using the newly introduced opera tion. In such cases the upper bound of the complexity of the algorithm is O (mn . log(mn)). A systematic comparison of this algorithm was done and the results show that this algorithm has the better average complexity than oth er published algorithms. The way of comparison and the results are given in a separate paper [Linear Algebra Appl. (submitted)]. Finally we prove that the problem can be solved in polynomial time also in a class of discrete s ets which is larger than the class of convex polyominoes, namely, in the cl ass of 8-connected convex sets. (C) 2001 Elsevier Science Inc. All rights r eserved.