Reconstructing hv-Convex Polyominoes from Orthogonal Projections
<|reference_start|>Reconstructing hv-Convex Polyominoes from Orthogonal Projections: 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.<|reference_end|>
@article{durr1999reconstructing,
    title={Reconstructing hv-Convex Polyominoes from Orthogonal Projections},
    author={Christoph Durr and Marek Chrobak},
    journal={Information Processing Letters, 69, 1999, 283-289},
    year={1999},
    archivePrefix={arXiv},
    eprint={cs/9906021},
    primaryClass={cs.DS}
}