Reconstruction of Discrete Sets with Absorption

  • Attila Kuba 
  • Maurice Nivat 
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 1953)


A generalization of a classical discrete tomography problem is considered: Reconstruct binary matrices from their absorbed row and columns sums, i.e., when some known absorption is supposed. It is math-ematically interesting when the absorbed projection of a matrix element is the same as the absorbed projection of the next two consecutive el-ements together. We show that, in this special case, the non-uniquely determined matrices contain a certain configuration of 0s and 1s, called alternatively corner-connected components. Furthermore, such matrices can be transformed into each other by switchings the 0s and 1s of these components.


  1. 1.
    Brualdi, R. A.: Matrices of zeros and ones with fixed row and column sums. Linear Algebra and Its Applications 33 (1980) 159–231 139zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Herman, G. T., Kuba, A. (Eds.): Discrete Tomography: Foundations, Algorithms and Applications. Birkhäuser, Boston (1999) 148Google Scholar
  3. 3.
    Kuba, A., Herman, G. T.: Discrete tomography: A historical overview. In [2] (1999) 3–34 139MathSciNetGoogle Scholar
  4. 4.
    Kuba, A., Nivat, M.: Reconstruction of discrete sets from projections in the case of absorption. Technical Reports, Institute of Informatics, University of Szeged (2000) 139, 141, 146, 147Google Scholar
  5. 5.
    Lothaire, M.: Combinatorics on Words. Cambridge University Press, Cambridge (1997) 138Google Scholar
  6. 6.
    Ryser, H. J.: Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9 (1957) 371–377 147zbMATHMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2000

Authors and Affiliations

  • Attila Kuba 
    • 1
  • Maurice Nivat 
    • 2
  1. 1.Laboratoire d’Informatique Algorithmique: Fondements et ApplicationsParisFrance
  2. 2.Department of Applied InformaticsUniversity of SzegedSzegedHungary

Personalised recommendations