Medians of polyominoes: A property for reconstruction
Elena Barcucci, Alberto Del Lungo, Maurice Nivat, Renzo Pinzani ยท International Journal of Imaging Systems and Technology ยท 1998
In a previous report, we studied the problem of reconstructing a discrete set ๐ฎ from its horizontal and vertical projections. We defined an algorithm that decides whether there is a convex polyomino ๐ฎ whose horizontal and vertical projections are given by (H, V), with H โ โm and V โ โn. If there is at least one convex polyomino with these projections, the algorithm reconstructs one of them in O(n4m4) time. In this article, we introduce the geometrical concept of a discrete set's medians. Starting out from this geometric property, we define some operations for reconstructing convex polyominoes from their projections (H, V). We are therefore able to define a new algorithm whose complexity is less than O(n2m2). Hence, this algorithm is much faster than the previous one. At the moment, however, we only have experimental evidence that this algorithm decides if there is a convex polyomino whose projections are equal to (H, V), for all (H, V) instances. ยฉ 1998 John Wiley & Sons, Inc. Int J Imaging Syst Technol, 9, 69โ77, 1998