Solving some instances of the two color problem.

The two color problem is an open problem in the field of discrete tomography, and it consists in determining a matrix, whose elements are of three different types, starting from its horizontal and vertical projections. It is known that the one color problem has a polynomial time reconstruction algorithm, while, with k > 2, the k-color problem is NP-complete. Thus, the two color problem constitutes an interesting example of a problem in the frontier between hard and easy problems.

In this talk we describe a linear time algorithm to solve a set of its instances, where some values of the horizontal and vertical projections are constant, while the others are upper bounded by a positive number proportional to dimension of the problem. Our algorithm relies on classical studies for the solution of the one color problem.