Comparison of algorithms for reconstructing hv-convex discrete sets

Three reconstruction algorithms to be used for reconstructing hv-convex discrete sets from their row and column sums are compared. All these algorithms have two versions. one for reconstructing hv-convex polyominoes and another one for reconstructing hv-convex 8-connected discrete sets. In both classes of discrete sets the algorithms are compared from the viewpoints of average execution time and memory complexities. Discrete sets with given sizes are generated with uniform distribution, and then reconstructed from their row and column sums. First we have implemented two previously published algorithms. According to our comparisons, the algorithm which was better from the viewpoint of worst time complexity was the worse from the viewpoint of average time complexity and memory requirements. Then, as a new method, a combination of the two algorithms was also implemented and it is shown that it inherits the best properties of the other two methods. (C) 2001 Elsevier Science Inc. All rights reserved.