Reconstructing hv-Convex Polyominoes from Orthogonal Projections
| dc.creator | Durr, Christoph | |
| dc.creator | Chrobak, Marek | |
| dc.date | 1999-06-22 | |
| dc.date.accessioned | 2026-07-07T03:24:10Z | |
| dc.date.available | 2026-07-07T03:24:10Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/cs/9906021 | |
| dc.identifier | http://arxiv.org/abs/cs/9906021 | |
| dc.identifier | Information Processing Letters, 69, 1999, 283-289 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/33221 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | F.2.2; G.2.1 | |
| dc.title | Reconstructing hv-Convex Polyominoes from Orthogonal Projections | |
| dc.type | text |