Bounds for approximate discrete tomography solutions

Abstract

In earlier papers we have developed an algebraic theory of discrete tomography. In those papers the structure of the functions $f:A\to \{0,1\}$ and $f:A\to \mathbb{Z}$ having given line sums in certain directions have been analyzed. Here $A$ was a block in ${\mathbb{Z}}^n$ with sides parallel to the axes. In the present paper we assume that there is noise in the measurements and (only) that $A$ is an arbitrary or convex finite set in ${\mathbb{Z}}^n$. We derive generalizations of earlier results. Furthermore we apply a method of Beck and Fiala to obtain results of he following type: if the line sums in $k$ directions of a function $h:A\to [0,1]$ are known, then there exists a function $f:A\to \{0,1\}$ such that its line sums differ by at most $k$ from the corresponding line sums of $h$.

16 pages