MEDIANS OF POLYOMINOES - A PROPERTY FOR RECONSTRUCTION

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.