Reconstructing convex polyominoes from horizontal and vertical projections

Reconstructing discrete bidimensional sets from their projections is involved in many different problems of computer-aided tomography, pattern recognition, image processing and data compression. In this paper, we examine the problem of reconstructing a discrete bidimensional set S satisfying some co...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 1996-03, Vol.155 (2), p.321-347
Main Authors: Barcucci, Elena, Del Lungo, Alberto, Nivat, Maurice, Pinzani, Renzo
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Reconstructing discrete bidimensional sets from their projections is involved in many different problems of computer-aided tomography, pattern recognition, image processing and data compression. In this paper, we examine the problem of reconstructing a discrete bidimensional set S satisfying some convexity conditions from its two orthogonal projections ( H, V). We develop an algorithm that starts out from ( H, V) and reconstructs set S, when S is a convex polyomino, in polynomial time. At the same time, we show that determining the existence of a row-convex (column-convex) polyomino or set with connected rows (columns) having assigned orthogonal projections ( H, V) is an NP-complete problem. Moreover, by using the algorithm to reconstruct convex polyominoes from their two orthogonal projections we prove that the numerical matching with target sums problem can be solved in polynomial time if its sequences are unimodal.
ISSN:0304-3975
1879-2294
DOI:10.1016/0304-3975(94)00293-2