Reconstruction of lattice sets from their horizontal, vertical and diagonal X-rays

In this paper, we study the problem of reconstructing a lattice set from its X-rays in a finite number of prescribed directions. The problem is NP-complete when the number of prescribed directions is greater than two. We provide a polynomial-time algorithm for reconstructing an interesting subclass...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2001-10, Vol.241 (1), p.65-78
Main Authors: Barcucci, Elena, Brunetti, Sara, Lungo, Alberto Del, Nivat, Maurice
Format: Article
Language:English
Subjects:
Combinatorial problems
Computational complexity
Discrete tomography
Lattice sets
Polynomial-time algorithm
Polyominoes
Tomography
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we study the problem of reconstructing a lattice set from its X-rays in a finite number of prescribed directions. The problem is NP-complete when the number of prescribed directions is greater than two. We provide a polynomial-time algorithm for reconstructing an interesting subclass of lattice sets (having some connectivity properties) from its X-rays in directions (1,0), (0,1) and (1,1). This algorithm can be easily extended to contexts having more than three X-rays.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(01)00110-8