Discrete tomography has strong connections with other mathematical fields, such as
number theory,
discrete mathematics,
computational complexity theory and
combinatorics. In fact, a number of discrete tomography problems were first discussed as combinatorial problems. In 1957,
H. J. Ryser found a necessary and sufficient condition for a pair of vectors being the two orthogonal projections of a discrete set. In the proof of his theorem, Ryser also described a reconstruction algorithm, the very first reconstruction algorithm for a general discrete set from two orthogonal projections. In the same year,
David Gale found the same consistency conditions, but in connection with the
network flow problem. Another result of Ryser's is the definition of the switching operation by which discrete sets having the same projections can be transformed into each other. The problem of reconstructing a binary image from a small number of projections generally leads to a large number of solutions. It is desirable to limit the class of possible solutions to only those that are typical of the class of the images which contains the image being reconstructed by using a priori information, such as convexity or connectedness.
Theorems • Reconstructing (finite) planar lattice sets from their 1-dimensional X-rays is an
NP-hard problem if the X-rays are taken from m\geq 3 lattice directions (for m=2 the problem is in P). • Coloring a grid using k colors with the restriction that each row and each column has a specific number of cells of each color is known as the (k-1)−atom problem in the discrete tomography community. The problem is NP-hard for k \geq 3 , see. For further results, see ==Algorithms==