论文标题
通过离散断层扫描II进行线性时间重建算法II
Algorithms for linear time reconstruction by discrete tomography II
论文作者
论文摘要
从其行总和中重建未知函数$ f $是离散断层扫描的目的。但是，两个主要方面阻止重建是一项容易的任务。通常，由于开关功能的存在，允许许多解决方案。即使有唯一性条件可用，有关重建算法的NP硬度的结果也会在某些集合中的$ f $值时，其实现效率低下。我们表明，当$ f $在一个字段或独特的分解域中，例如$ \ r $或$ \ z $时，情况并非如此。我们提出了一个线性时间重建算法（在方向数和网格的大小中），该算法输出了开关域之外的所有点的原始函数值。自由选择的值分配给其他要点，即具有歧义的值。提供了示例。
The reconstruction of an unknown function $f$ from its line sums is the aim of discrete tomography. However, two main aspects prevent reconstruction from being an easy task. In general, many solutions are allowed due to the presence of the switching functions. Even when uniqueness conditions are available, results about the NP-hardness of reconstruction algorithms make their implementation inefficient when the values of $f$ are in certain sets. We show that this is not the case when $f$ takes values in a field or a unique factorization domain, such as $\R$ or $\Z$. We present a linear time reconstruction algorithm (in the number of directions and in the size of the grid), which outputs the original function values for all points outside of the switching domains. Freely chosen values are assigned to the other points, namely, those with ambiguities. Examples are provided.
