On the algorithmic inversion of the discrete Radon transform

✍ Scribed by Peter Gritzmann; Sven de Vries

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 157 KB
• Volume: 281
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00023-3

✦ Synopsis

The present paper deals with the computational complexity of the discrete inverse problem of reconstructing ÿnite point sets and more general functionals with ÿnite support that are accessible only through some of the values of their discrete Radon transform. It turns out that this task behaves quite di erently from its well-studied companion problem involving 1-dimensional X-rays. Concentrating on the case of coordinate hyperplanes in R d and on functionals : Z d → D with D ∈ {{0; 1; : : : ; r}; N0} for some arbitrary but ÿxed r, we show in particular that the problem can be solved in polynomial time if information is available for m such hyperplanes when m 6 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.