Algebraic aspects of discrete tomography (Q2717078)

Let \(m,n\in \mathbb Z\) and \(A=\{(i,j)\in\mathbb Z^2 : 0\leq i < m,\;0\leq j < n\}\). If further \((a,b)\) is a pair of coprime integers, then a line with direction \((a,b)\) is a line in the \((x,y)\)-plane of the form \(ay=bx+t\) with \(t\in\mathbb Z\). The main problem of discrete tomography is to reconstruct a function \(f:A\to \{0,1\}\) if only the sums of its values along all lines in a finite number of directions are given, i.e., all of the sums \(\sum_{{a_dj=b_di+t \atop (i,j)\in A}} f(i,j)\) for \(d=1,\dots,k\) and \(t\in \mathbb Z\). In the present paper the authors first give a characterization of the functions \(g\) with zero line sums (for an arbitrary finite set of directions \(S=\{(a_d,b_d)\}_{d=1}^k\)). Then they use their theory to construct an algorithm, polynomial in \(\max\{m,n\}\), which finds a function \(g:A\to \mathbb Z\) with the same line sums as \(f\) and which satisfies \(| g(i,j)| \leq 2^{k-1}+1\) on average (i.e., the 2-norm of \(g\) is smaller than \((2^{k-1}+1)\sqrt{mn}\)).