Reconstructing Binary Matrices under Window Constraints from their Row and Column Sums

• Autorzy: Alpers, A. , Gritzmann, P.
• Języki publikacji: EN

Abstrakty

EN

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 polynomialtime solvability to NP-hardness.

Słowa kluczowe

EN

matrices; inversion; additional member system; constraints; discrete tomography; polynomial time algorithm

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 155, nr 4
• Strony: 321--340
• Opis fizyczny: Bibliogr. 20 poz., rys., tab.

Twórcy

autor

Alpers, A.

• Zentrum Mathematik, Technische Universität München, D-85747 Garching bei München, Germany,

autor

Gritzmann, P.

• Zentrum Mathematik, Technische Universität München, D-85747 Garching bei München, Germany,

Bibliografia

• [1] Ryser HJ. Combinatorial properties of matrices of zeros and ones. Canad. J. Math., 1957. 9(1):371–377. doi:10.1007/978-0-8176-4842-8_18.
• [2] Schwander P, Kisielowski C, Baumann FH, Kim Y, Ourmazd A. Mapping projected potential, interfacial roughness, and composition in general crystalline solids by quantitative transmission electron microscopy. Phys. Rev. Lett., 1993. 71(25):4150–4153. doi:10.1103/PhysRevLett.71.4150.
• [3] Kisielowski C, Schwander P, Baumann FH, Seibt M, Kim Y, Ourmazd A. An approach to quantitative high-resolution transmission electron microscopy of crystalline materials. Ultramicroscopy, 1995. 58(2):131–155. doi:10.1016/0304-3991(94)00202-X.
• [4] Gardner RJ, Gritzmann P. Discrete tomography: Determination of finite sets by X-rays. Trans. Amer. Math. Soc., 1997. 349(6):2271–2295. doi:10.1090/S0002-9947-97-01741-8.
• [5] Gritzmann P. On the Reconstruction of Finite Lattice Sets from their X-Rays. In: Discrete Geometry for Computer Imagery (Eds.: E. Ahronovitz and C. Fiorio), DCGI’97, Lecture Notes on Computer Science 1347, Springer. 1997 pp. 19–32. doi:10.1007/BFb0024827.
• [6] Aert SV, Batenburg KJ, Rossell MD, Erni R, Tendeloo GV. Three-dimensional atomic imaging of crystalline nanoparticles. Nature, 2011. 470(7334):374–376. doi:doi:10.1038/nature09741.
• [7] Herman GT, Kuba (eds) A. Discrete Tomography: Foundations, Algorithms and Applications. Birkhäuser, Boston, 1999. ISBN 978-0-8176-4101-6. doi:10.1007/978-1-4612-1568-4.
• [8] Herman GT, Kuba (eds) A. Advances in Discrete Tomography and its Applications. Birkhäuser, Boston, 2007. ISBN 978-0-8176-3614-2. doi:10.1007/978-0-8176-4543-4.
• [9] Fishburn P, Lagarias J, Reeds J, Shepp L. Sets uniquely determined by projections on axes. II: Discrete case. Discrete Math., 1991. 91(2):149–159. doi:10.1016/0012-365X(91)90106-C.
• [10] Aharoni R, Herman GT, Kuba A. Binary vectors partially determined by linear equation systems. Discrete Math., 1997. 171(1-3):1–16. doi:10.1016/S0012-365X(96)00068-4.
• [11] Gritzmann P, Langfeld B, Wiegelmann M. Uniqueness in Discrete Tomography: Three Remarks and a Corollary. SIAM J. Discrete Math., 2011. 25(4):1589–1599. doi:10.1137/100803262.
• [12] Alpers A, Gritzmann P. Dynamic discrete tomography, 2017. Manuscript.
• [13] Alpers A, Gritzmann P, Moseev D, Salewski M. 3D Particle Tracking Velocimetry using Dynamic Discrete Tomography. Comput. Phys. Commun., 2015. 187(1):130–136. doi:10.1016/j.cpc.2014.10.022.
• [14] Zhu J, Gao J, Ehn A, Aldén M, Li Z, Moseev D, Kusano Y, Salewski M, Alpers A, Gritzmann P, Schwenk M. Measurements of 3D Slip Velocities and Plasma Column Lengths of a Gliding Arc Discharge. Appl. Phys. Lett., 2015. 106(4):044101–1–4. doi:10.1063/1.4906928.
• [15] Alpers A, Gritzmann P. On double-resolution imaging and discrete tomography, 2017. Submitted, URL http://arxiv.org/abs/1701.04399.
• [16] Schrijver A. Theory of Linear and Integer Programming. John Wiley & Sons, Chichester, UK, 1986. ISBN 0-471-90854-1.
• [17] Dürr C, Guiñez F, Matamala M. Reconstructing 3-Colored Grids from Horizontal and Vertical Projections is NP-Hard: A Solution to the 2-Atom Problem in Discrete Tomography. SIAM J. Discrete Math, 2012. 26(1):330–352. doi:10.1137/100799733.
• [18] Cook SA. The complexity of theorem-proving procedures. In: Proc. 3rd Ann. ACM Symp. Theory of Computing. ACM, 1971 pp. 151–158. doi:10.1145/800157.805047.
• [19] Frosini A, Nivat M. Binary matrices under the microscope: A tomographical problem. Theor. Comput. Sci., 2007. 370(1-3):201–217. doi:10.1016/j.tcs.2006.10.030.
• [20] Frosini A, Nivat M, Rinaldi S. Scanning integer matrices by means of two rectangular windows. Theor. Comput. Sci., 2008. 406(1-2):90–96. doi:10.1016/j.tcs.2008.07.016.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).

Identyfikatory

DOI

10.3233/FI-2017-1588