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

Extract from the authors' abstract: We examine the problem of reconstructing a discrete two-dimensional set from its two orthogonal projection \((H,V)\) when the set satisfies some convexity conditions. We show that the algorithm of an earlier paper is a heuristic algorithm but it does not solve the problem for all \((H,V)\) instances. We propose a modification of this algorithm solving the problem for all \((H,V)\) instances, by starting to build the ``spline''. The complexity of our reconstruction algorithm is \(O(mn.\log(mn).\min\{m^2,n^2\})\) in the worst case. According to our experimental results, in 99\% of the cases, the algorithm is able to reconstruct a solution without using the newly introduced operation. In such cases, the upper bound of the complexity of the algorithm is \(O(mn.\log(mn))\). Finally, we prove that the problem can be solved in polynomial time also in a class of discrete sets which is larger than the class of convex polyominoes.