On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional X-rays

Authors
Brunetti, S Del Lungo, A Gerard, Y
Citation
S. Brunetti et al., On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional X-rays, LIN ALG APP, 339, 2001, pp. 59-73
Citations number
13
Categorie Soggetti
Mathematics
Journal title
LINEAR ALGEBRA AND ITS APPLICATIONS
ISSN journal
00243795 → ACNP
Volume
339
Year of publication
2001
Pages
59 - 73
Database
ISI
SICI code
0024-3795(200112)339:<59:OTCCOR>2.0.ZU;2-J
Abstract
A generalization of a classical discrete tomography problem is considered: reconstruct three-dimensional lattice sets from their two-dimensional X-ray s parallel to three coordinate planes. First, we prove that this reconstruc tion problem is NP-hard. Then we propose some greedy algorithms that provid e approximate solutions of the problem. (C) 2001 Elsevier Science Inc. All rights reserved.