Paper Info
Title
On the algorithmic inversion of the discrete Radon transform
Abstract
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 Rd and on functionals ¿:Zd¿D with D¿{{0,1,¿,r},N0} 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,¿,r}. However, for D=N0, 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.
Year
DOI
Venue
2002
10.1016/S0304-3975(02)00023-3
Theor. Comput. Sci.
Keywords
DocType
Volume
general functionals,algorithmic inversion,radon transform,68r05,discrete tomography,well-studied companion problem,related counting problem,68u10,discrete radon,90c10,computational complexity,contingency table,p. similar result,discrete inverse problem,polynomial-time algorithm,finite point set,finite support,np-hard,1-dimensional x-ray
Journal
281
Issue
ISSN
Citations 
1
Theoretical Computer Science
7
PageRank 
References 
Authors
0.87
8
2
Name
Order
Citations
PageRank
Peter Gritzmann141246.93
Sven de Vries252258.84