In a previous report, we studied the problem of recon-Kuba's heuristic algorithm [7] reconstructs some convex sets. structing a discrete set S from its horizontal and vertical projections.
Some of the properties imposed on the sets eliminate all ambigu-
We defined an algorithm that decides whether there is a convex polyity [4], while some others only partially reduce it [12]. We omino S whose horizontal and vertical projections are given by (H, also noted that ambiguity reduction does not always facilitate V ), with H β β«ήβ¬ m and V β β«ήβ¬ n . If there is at least one convex polyomino set reconstruction. As a matter of fact, when certain convexity with these projections, the algorithm reconstructs one of them in conditions are imposed, the problem becomes NP-complete O(n 4 m 4 ) time. In this article, we introduce the geometrical concept [13,14]. of a discrete set's medians. Starting out from this geometric property,
In a previous paper of ours [14], we studied this problem we define some operations for reconstructing convex polyominoes with respect to some classes of discrete sets on which some from their projections ( H, V ). We are therefore able to define a new algorithm whose complexity is less than O(n 2 m 2 ). Hence, this algo-connectivity constraints were imposed, and in particular, we derithm is much faster than the previous one. At the moment, however, fine an algorithm for reconstructing convex polyominoes. A polywe only have experimental evidence that this algorithm decides if omino P is a discrete set in which for any pair of cells of P there there is a convex polyomino whose projections are equal to (H, V ), exists a lattice path in P connecting them (Fig. 1). A lattice path for all ( H, V ) instances.