Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms

Details Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms

1999-06-21

arxiv.org/abs/cs/9906018v1

Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, LNCS vol 1450, 185-193, 1998

Computer Science

Data Structures and Algorithms

Scientific paper

We address a discrete tomography problem that arises in the study of the atomic structure of crystal lattices. A polyatomic structure T can be defined as an integer lattice in dimension D>=2, whose points may be occupied by $c$ distinct types of atoms. To ``analyze'' T, we conduct ell measurements that we call_discrete X-rays_. A discrete X-ray in direction xi determines the number of atoms of each type on each line parallel to xi. Given ell such non-parallel X-rays, we wish to reconstruct T. The complexity of the problem for c=1 (one atom type) has been completely determined by Gardner, Gritzmann and Prangenberg, who proved that the problem is NP-complete for any dimension D>=2 and ell>=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 ell=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 axis-parallel X-rays. They conjecture that the problem remains NP-complete for c=3,4,5, although, as they point out, the proof idea does not seem to extend to c<=5. We resolve the conjecture by proving that the problem is indeed NP-complete for c>=3 in 2D, even for 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.

Affiliated with

Also associated with

No associations

Rating

Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms 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 Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reconstructing Polyatomic Structures from Discrete X-Rays: NP-Completeness Proof for Three Atoms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-395233