Reconstructing Hv-Convex Polyominoes from Orthogonal Projections
Title | Reconstructing Hv-Convex Polyominoes from Orthogonal Projections |
Publication Type | Technical Report |
Year of Publication | 1998 |
Authors | Chrobak, M., & Dürr C. |
Other Numbers | 1141 |
Keywords | Combinatorial problems, Discrete Tomography, polyominoes |
Abstract | 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 http://www.icsi.berkeley.edu/~cduerr/Xray/Polyomino/polyomino.html. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1998/tr-98-020.pdf |
Bibliographic Notes | ICSI Technical Report TR-98-020 |
Abbreviated Authors | M. Chrobak and C. Dürr |
ICSI Publication Type | Technical Report |