Algorithms for linear time reconstruction by discrete tomography

We present an algorithm that for any given rectangular grid A∈Z2 and set of directions D computes in linear time the values of any function f:A→R outside the convex hull of the union of the switching domains from its line sums in the directions of D. Moreover, the algorithm reconstructs f completely if there are no switching domains. We present a simpler algorithm in case the directions satisfy some monotonicity condition. Finally, for given A we propose how to choose the set D so that only a small number of directions is needed to reconstruct any f from its line sums in the directions of D.