Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2001 | 10.1016/S0012-365X(01)00110-8 | Discrete Mathematics |
Keywords | Field | DocType |
polyominoes,computational complexity,lattice set,combinatorial problems,polynomial-time algorithm,discrete tomography,tomography,diagonal x-ray,lattice sets | Diagonal,Discrete mathematics,Combinatorics,Finite set,Lattice (order),Subclass,Discrete tomography,Polyomino,Tomography,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
241 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
8 | 0.89 | 8 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Elena Barcucci | 1 | 306 | 59.66 |
Sara Brunetti | 2 | 122 | 16.23 |
Alberto Del Lungo | 3 | 376 | 44.84 |
Maurice Nivat | 4 | 1261 | 277.74 |