Publication Details
Title: Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms
Author: M. Chrobak and C. Dürr
Group: ICSI Technical Reports
Date: April 1998
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1998/tr-98-012.pdf
Overview:
We address a discrete tomography problem arising in the study of the atomic structure of crystal lattices. A polyatomic structure T is an integer lattice in dimension D ≥ 2, whose points may be occupied by c types of atoms. To “analyze” T, we conduct ℓ measurements that we refer to as discrete X-rays. A discrete X-ray in direction ξ determines the number of atoms of each type on each line parallel to ξ. Given such ℓ non-parallel X-rays, we wish to reconstruct T. The complexity of the problem for c = 1 (one atom) has been completely determined by Gardner, Gritzmann and Prangerberg, who proved that the problem is NP-complete for any dimension D ≥ 2 and ℓ ≥ 3 non-parallel X-rays, and that it can be solved in polynomial time otherwise. The NP-completeness result above clearly extends to any c ≥ 2, and therefore when studying the polyatomic case we can assume that ℓ = 2. As shown in another article by the same authors, this problem is also NP-complete for c ≥ 6 atoms, even for dimension D = 2 and for the axis-parallel X-rays. The authors of that article conjecture that the problem remains NP-complete for c = 3, 4, 5. We resolve this conjecture by proving that the problem is indeed NP-complete for c ≥ 3 in 2D, even for the axis-parallel X-rays. Our construction relies heavily on some structure results for the realizations of 0-1 matrices with given row and column sums. Keywords: Discrete Tomography, X-rays, HRTEM, QUANTITEM, Multicommodity flow, Contigency table.
Bibliographic Information:
ICSI Technical Report TR-98-012
Bibliographic Reference:
M. Chrobak and C. Dürr. Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms. ICSI Technical Report TR-98-012, April 1998
Author: M. Chrobak and C. Dürr
Group: ICSI Technical Reports
Date: April 1998
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1998/tr-98-012.pdf
Overview:
We address a discrete tomography problem arising in the study of the atomic structure of crystal lattices. A polyatomic structure T is an integer lattice in dimension D ≥ 2, whose points may be occupied by c types of atoms. To “analyze” T, we conduct ℓ measurements that we refer to as discrete X-rays. A discrete X-ray in direction ξ determines the number of atoms of each type on each line parallel to ξ. Given such ℓ non-parallel X-rays, we wish to reconstruct T. The complexity of the problem for c = 1 (one atom) has been completely determined by Gardner, Gritzmann and Prangerberg, who proved that the problem is NP-complete for any dimension D ≥ 2 and ℓ ≥ 3 non-parallel X-rays, and that it can be solved in polynomial time otherwise. The NP-completeness result above clearly extends to any c ≥ 2, and therefore when studying the polyatomic case we can assume that ℓ = 2. As shown in another article by the same authors, this problem is also NP-complete for c ≥ 6 atoms, even for dimension D = 2 and for the axis-parallel X-rays. The authors of that article conjecture that the problem remains NP-complete for c = 3, 4, 5. We resolve this conjecture by proving that the problem is indeed NP-complete for c ≥ 3 in 2D, even for the axis-parallel X-rays. Our construction relies heavily on some structure results for the realizations of 0-1 matrices with given row and column sums. Keywords: Discrete Tomography, X-rays, HRTEM, QUANTITEM, Multicommodity flow, Contigency table.
Bibliographic Information:
ICSI Technical Report TR-98-012
Bibliographic Reference:
M. Chrobak and C. Dürr. Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms. ICSI Technical Report TR-98-012, April 1998