Reconstructing Hv-Convex Polyominoes from Orthogonal Projections

TitleReconstructing Hv-Convex Polyominoes from Orthogonal Projections
Publication TypeTechnical Report
Year of Publication1998
AuthorsChrobak, M., & Dürr C.
Other Numbers1141
KeywordsCombinatorial problems, Discrete Tomography, polyominoes

Tomography is the area of reconstructing objects from projections. Here we wish to reconstruct a set of cells in a two dimensional grid, given the number of cells in every row and column. The set is required to be an hv-convex polyomino, that is all its cells must be connected and the cells in every row and column must be consecutive.A simple, polynomial algorithm for reconstructing hv-convex polyominoes is provided, which is several orders of magnitudes faster than the best previously known algorithm from Barcucci et al. In addition, the problem of reconstructing a special class of centered hv-convex polyominoes is addressed. (An object is centered if it contains a row whose length equals the total width of the object). It is shown that in this case the reconstruction problem can be solved in linear time.Implementations are available from

Bibliographic Notes

ICSI Technical Report TR-98-020

Abbreviated Authors

M. Chrobak and C. Dürr

ICSI Publication Type

Technical Report