Reconstruction of 8-connected but not 4-connected \(hv\)-convex discrete sets (Q1775617)

The authors consider the reconstruction of 8-connected but not 4-connected \(hv\)-convex discrete sets from projections, which is a very important problem in discrete tomography. A new algorithm is presented with worst case complexity of \(O(mn\min\{m,n\})\) to reconstruct all sets from horizontal and vertical projections. By using in addition the diagonal projections the complexity of the algorithm can be reduced to \(O(mn)\) in which case there is a unique solution. Possible generalizations are also briefly discussed to more general classes. Numerical examples illustrate the algorithms.