Publication Details
Title: Reconstructing Hv-Convex Polyominoes from Orthogonal Projections
Author: M. Chrobak and C. Dürr
Group: ICSI Technical Reports
Date: July 1998
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1998/tr-98-020.pdf
Overview:
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. Keywords: Combinatorial problems, discrete tomography, polyominoes
Bibliographic Information:
ICSI Technical Report TR-98-020
Bibliographic Reference:
M. Chrobak and C. Dürr. Reconstructing Hv-Convex Polyominoes from Orthogonal Projections. ICSI Technical Report TR-98-020, July 1998
Author: M. Chrobak and C. Dürr
Group: ICSI Technical Reports
Date: July 1998
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1998/tr-98-020.pdf
Overview:
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. Keywords: Combinatorial problems, discrete tomography, polyominoes
Bibliographic Information:
ICSI Technical Report TR-98-020
Bibliographic Reference:
M. Chrobak and C. Dürr. Reconstructing Hv-Convex Polyominoes from Orthogonal Projections. ICSI Technical Report TR-98-020, July 1998