2017/02/20 by Andreas Alpers, Alpers, Andreas, Peter Gritzmann +1 · 1 citation
Computer Science · Medicine · #49N45 #68Q25 #68R05 #94A08 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Medical Image Segmentation Techniques #Medical Imaging Techniques and Applications
paper · pdf · doi:10.48550/arxiv.1702.06121
openalex publication_date 2017/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The present paper deals with the discrete inverse problem of reconstructing binary matrices from their row and column sums under additional constraints on the number and pattern of entries in specified minors. While the classical consistency and reconstruction problems for two directions in discrete tomography can be solved in polynomial time, it turns out that these window constraints cause various unexpected complexity jumps back and forth from polynomial-time solvability to ℕℙ-hardness.