On the computational complexity of determining polyatomic structures by X-rays

DOI10.1016/S0304-3975(97)00298-3zbMath1005.82035MaRDI QIDQ1575953

D. Prangenberg, Peter Gritzmann, Richard J. Gardner

Publication date: 23 August 2000

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

zbMATH Keywords

latticecomputational complexityschedulingNP-completenesspolynomial-time algorithmtomographydiscrete tomographycontingency tabledata security

Mathematics Subject Classification ID

Biomedical imaging and signal processing (92C55) Statistical mechanics of crystals (82D25) Radon transform (44A12) Enumerative combinatorics (05A99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (15)

Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem ⋮ Regular switching components ⋮ Error Correction for Discrete Tomography ⋮ On tiling under tomographic constraints. ⋮ On polyatomic tomography over abelian groups: some remarks on consistency, tree packings and complexity ⋮ 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 ⋮ Tile-packing tomography is \(\mathbb{NP}\)-hard ⋮ Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms ⋮ Algorithms for linear time reconstruction by discrete tomography. II ⋮ Approximating hv-Convex Binary Matrices and Images from Discrete Projections ⋮ Solving Some Instances of the 2-Color Problem ⋮ Using graphs for some discrete tomography problems

Cites Work

• Unnamed Item
• The complexity of facets (and some facets of complexity)
• On joint realization of (0,1) matrices
• Sets uniquely determined by projections on axes. II: Discrete case
• On the computational complexity of reconstructing lattice sets from their \(X\)-rays
• On the unique satisfiability problem
• Three-dimensional Statistical Data Security Problems
• The reconstruction of binary patterns from their projections

This page was built for publication: On the computational complexity of determining polyatomic structures by X-rays