Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms

DOI10.1016/S0304-3975(99)00325-4zbMath0974.68219MaRDI QIDQ5941271

Christoph Dürr, Marek Chrobak

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

discrete tomographyhigh-resolution transmission electron microscopemulti-commodity max flow

Mathematics Subject Classification ID

Biomedical imaging and signal processing (92C55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (18)

The NP-completeness of a tomographical problem on bicolored domino tilings ⋮ Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem ⋮ Tiling with bars under tomographic constraints. ⋮ On tiling under tomographic constraints. ⋮ A reconstruction algorithm for a subclass of instances of the 2-color problem ⋮ A formulation of the wide partition conjecture using the atom problem in discrete tomography ⋮ Solving the Two Color Problem: An Heuristic Algorithm ⋮ Approximating Bicolored Images from Discrete Projections ⋮ Reconstruction of binary matrices under fixed size neighborhood constraints ⋮ On the use of graphs in discrete tomography ⋮ On the use of graphs in discrete tomography ⋮ A solvable case of image reconstruction in discrete tomography ⋮ Reconstruction of domino tiling from its two orthogonal projections ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Reconstructing \(hv\)-convex multi-coloured polyominoes ⋮ Solving Some Instances of the 2-Color Problem ⋮ Using graphs for some discrete tomography problems ⋮ Reconstruction of binary matrices under adjacency constraints

Cites Work

• Matrices of zeros and ones with fixed row and column sum vectors
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• On the computational complexity of determining polyatomic structures by X-rays
• On the Complexity of Timetable and Multicommodity Flow Problems
• Three-dimensional Statistical Data Security Problems
• The reconstruction of binary patterns from their projections
• Unnamed Item
• Unnamed Item

This page was built for publication: Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms