Comparison of algorithms for reconstructing hv-convex discrete sets

Three reconstruction algorithms to be used for reconstructing hv-convex dis crete sets from their row and column sums are compared. All these algorithm s have two versions. one for reconstructing hv-convex polyominoes and anoth er one for reconstructing hv-convex 8-connected discrete sets. In both clas ses of discrete sets the algorithms are compared from the viewpoints of ave rage 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 al gorithms. 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 Elsevie r Science Inc. All rights reserved.