×

On the algorithmic inversion of the discrete Radon transform. (English) Zbl 0997.68151

Summary: The present paper deals with the computational complexity of the discrete inverse problem of reconstructing finite point sets and more general functionals with finite support that are accessible only through some of the values of their discrete Radon transform. It turns out that this task behaves quite differently from its well-studied companion problem involving 1-dimensional X-rays. Concentrating on the case of coordinate hyperplanes in \(R^{d}\) and on functionals \(\psi: Z^{d}\rightarrow D\) with \(D\in{{0,1,\ldots,r},N_{0}}\) for some arbitrary but fixed \(r,\) we show in particular that the problem can be solved in polynomial time if information is available for \(m\) such hyperplanes when \(m<d-1\) but is \(NP\)-hard for \(m=d\) and \(D=\{0,1,\ldots,r\}\). However, for \(D=N_{0},\) a case that is relevant in the context of contingency tables, the problem is still in \(P.\) Similar results are given for the task of determining the uniqueness of a given solution and for a related counting problem.

MSC:

68U10 Computing methodologies for image processing
68R05 Combinatorics in computer science
90C10 Integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brunetti, S.; Del Lungo, A.; Gerard, Y., On the computational complexity of reconstructing three-dimensional lattice sets from their two-dimensional X-rays, Linear Algebra Appl., 339, 59-73 (2001) · Zbl 1007.65109
[2] Brunetti, S.; Del Lungo, A.; Gritzmann, P.; de Vries, S., On the reconstruction of permutation and partition sets under tomographic constraints, Manuscript, 13 (2001)
[3] Chang, S. K., The reconstruction of binary patterns from their projections, Commun. ACM, 14, 1, 21-25 (1971) · Zbl 0214.42603
[4] Fishburn, P.; Schwander, P.; Shepp, L.; Vanderbei, R. J., The discrete Radon transform and its approximate inversion via linear programming, Discrete Appl. Math., 75, 1, 39-61 (1997) · Zbl 0879.68103
[5] Fishburn, P. C.; Lagarias, J. C.; Reeds, J. A.; Shepp, L. A., Sets uniquely determined by projections on axes II: Discrete case, Discrete Math., 91, 2, 149-159 (1991) · Zbl 0752.44002
[6] Gardner, R.; Gritzmann, P., Uniqueness and complexity in discrete tomography, (Herman, G.; Kuba, A., Discrete Tomography: Foundations, Algorithms, Applications (1999), Birkhäuser: Birkhäuser Boston), 85-113 · Zbl 0964.65146
[7] R.J. Gardner, P. Gritzmann, D. Prangenberg, in: R.A. Melter, A.Y. Wu, L. Latecki (Eds.), On the Reconstruction of Binary Images from their Discrete Radon Transforms, Vision Geometry V, Society of Photo-Optical Instrumentation Engineers Proceedings, Vol. 2826, 1996, pp. 121-132.; R.J. Gardner, P. Gritzmann, D. Prangenberg, in: R.A. Melter, A.Y. Wu, L. Latecki (Eds.), On the Reconstruction of Binary Images from their Discrete Radon Transforms, Vision Geometry V, Society of Photo-Optical Instrumentation Engineers Proceedings, Vol. 2826, 1996, pp. 121-132.
[8] Gardner, R. J.; Gritzmann, P.; Prangenberg, D., On the computational complexity of reconstructing lattice sets from their X-rays, Discrete Math., 202, 45-71 (1999) · Zbl 0947.68160
[9] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-completeness (1979), Freeman · Zbl 0411.68039
[10] Gritzmann, P., On the reconstruction of finite lattice sets from their X-rays, (Ahronovitz, E.; Fiorio, C., Proc. 7th Internat. Workshop, DGCI ’97, Montpellier, France. Proc. 7th Internat. Workshop, DGCI ’97, Montpellier, France, Lecture Notes in Computer Science, Vol. 1347 (1997), Springer), 19-32
[11] P. Gritzmann, S. de Vries, Reconstructing crystalline structures from few images under high resolution transmission electron microscopy, in: W. Jäger (Ed.), Mathematics: Key Technology for the Future, Springer, 2002, in print.; P. Gritzmann, S. de Vries, Reconstructing crystalline structures from few images under high resolution transmission electron microscopy, in: W. Jäger (Ed.), Mathematics: Key Technology for the Future, Springer, 2002, in print. · Zbl 1034.82061
[12] (Herman, G. T.; Kuba, A., Discrete Tomography: Foundations, Algorithms, and Applications (1999), Birkhäuser: Birkhäuser Boston) · Zbl 0946.00014
[13] Irving, R. W.; Jerrum, M. R., Three-dimensional statistical data security problems, SIAM J. Comput., 23, 170-184 (1994) · Zbl 0802.68046
[14] Johnson, D. S., A catalog of complexity classes, (van Leeuwen, J., Handbook of Theoretical Computer Science, Vol. A (1990), Elsevier Science Publishers B.V.,: Elsevier Science Publishers B.V., Amsterdam), 69-161 · Zbl 0900.68246
[15] Ryser, H. J., Combinatorial properties of matrices of zeros and ones, Canad. J. Math., 9, 371-377 (1957) · Zbl 0079.01102
[16] H.J. Ryser, Combinatorial Mathematics, Mathematical Association of America and Quinn & Boden, Rahway, NJ, 1963.; H.J. Ryser, Combinatorial Mathematics, Mathematical Association of America and Quinn & Boden, Rahway, NJ, 1963. · Zbl 0112.24806
[17] Slump, C. H.; Gerbrands, J. J., A network flow approach to reconstruction of the left ventricle from two projections, Comput. Graphics Image Process., 18, 18-36 (1982)
[18] Tardos, É., A strongly polynomial algorithm to solve combinatorial linear programs, Operations Research, 34, 2, 250-256 (1986) · Zbl 0626.90053
[19] Torres-Cházaro, A.; Vallejo, E., Sets of uniqueness and minimal matrices, J. Algebra, 208, 444-451 (1998) · Zbl 0954.05003
[20] M. Wiegelmann, Gröbner bases and primal algorithms in discrete tomography, Ph.D. thesis, Technische Universität München, 1998.; M. Wiegelmann, Gröbner bases and primal algorithms in discrete tomography, Ph.D. thesis, Technische Universität München, 1998.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.