E. Barcucci et al., MEDIANS OF POLYOMINOES - A PROPERTY FOR RECONSTRUCTION, International journal of imaging systems and technology, 9(2-3), 1998, pp. 69-77
In a previous report, we studied the problem of reconstructing a discr
ete set S from its horizontal and vertical projections. We defined an
algorithm that decides whether there is a convex polyomino S whose hor
izontal and vertical projections are given by (H, V), with H is an ele
ment of N-m and V is an element of N-n. If there is at least one conve
x polyomino with these projections, the algorithm reconstructs one of
them in O(n(4)m(4)) time. In this article, we introduce the geometrica
l concept of a discrete set's medians. Starting out from this geometri
c property, we define some operations for reconstructing convex polyom
inoes 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
algorithm is much faster than the previous one. At the moment, however
, we only have experimental evidence that this algorithm decides if th
ere is a convex polyomino whose projections are equal to (H, V), for a
ll (H, V) instances. (C) 1998 John Wiley & Sons, Inc.