Linear time reconstruction by discrete tomography in three dimensions
Matthew Ceko, Silvia M.C. Pagani, Rob Tijdeman · arXiv (Cornell University) · 2020
The goal of discrete tomography is to reconstruct an unknown function $f$ via a given set of line sums. In addition to requiring accurate reconstructions, it is favourable to be able to perform the task in a timely manner. This is complicated by the presence of switching functions, or ghosts, which allow many solutions to exist in general. In this paper we consider the case of a function $f : A \to \mathbb{R}$ where $A$ is a finite grid in $\mathbb{Z}^3$. Previous work has shown that in the two-dimensional case it is possible to determine all solutions in parameterized form in linear time (with respect to the number of directions and the grid size) regardless of whether the solution is unique. In this work, we show that a similar linear method exists in three dimensions under the condition of nonproportionality. This is achieved by viewing the three-dimensional grid along each 2D coordinate plane, effectively solving the problem with a series of 2D linear algorithms. We show that the condition of nonproportionality is fulfilled in the case of three-dimensional boundary ghosts, which motivated this research.