A linear time approach to three-dimensional reconstruction by discrete tomography

Contributions to Discrete Mathematics, vol. 19, pp. 222–240

Abstract

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 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. We show that the condition of nonproportionality is fulfilled in the case of three-dimensional boundary ghosts.

Authors 3

1. Matthew Ceko

   Monash University

   Affiliation as printed

   Monash University

2. Silvia M.C. Pagani

   Università Cattolica del Sacro Cuore

   Affiliation as printed

   Università Cattolica del Sacro Cuore

3. Rob Tijdeman Aachen

   Leiden University

   Affiliation as printed

   Leiden University