Analysis and optimization of an algorithm for discrete tomography

Binary tomography is concerned with recovering binary images from a finite number of discretely sampled projections. Hajdu and Tijdeman outlined an algorithm for this type of problem. In this paper we analyze the algorithm and present several ways of improving the time complexity. We also give the results of experiments with an optimized version which is much faster than the original implementation, up to a factor of 50 or more (depending on the problem instance).