Reconstructing hv-Convex Polyominoes from Orthogonal Projections

Details Reconstructing hv-Convex Polyominoes from Orthogonal Projections Reconstructing hv-Convex Polyominoes from Orthogonal Projections

1999-06-22

arxiv.org/abs/cs/9906021v1

Information Processing Letters, 69, 1999, 283-289

Computer Science

Data Structures and Algorithms

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Reconstructing hv-Convex Polyominoes from Orthogonal Projections does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Reconstructing hv-Convex Polyominoes from Orthogonal Projections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstructing hv-Convex Polyominoes from Orthogonal Projections will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-386454