Last update was may'09.

Problems in discrete tomography

On this page you see grids, with numbers on the rows and columns. They represent requirements of how many objects have to be placed in the rows or columns. Each time you place an object on the grid, the corresponding numbers decrease. The goal is to make them all zero.

The two atom problem


 Can you toggle the cell-colors by mouse-clicks such that all numbers are zero? This problem has been shown to be NP-complete [2].

In this problem there are two colors (not counting white indicating an empty cell). However for a single color the problem is easy [5] and can be solved in time O(n log n), where n is the side length of the grid. The first NP-completness proof for a constant number of colors was [4].

The domino-tiling problem

Can you drag the dominoes on the grid such that all the numbers become zero? This problem has been solved in 2007 by Nicolas Thiant in his PhD who gave a polynomial time algorithm for it, for the case the dominoes have to tile completely the grid. Otherwise the problem is NP-complete [1].

Reconstructing convex polyominoes


 Can you select cells of the grid with the mouse such that (1) all number are zero and (2) the convex hull (in red) contains only selected cells? This is an open problem. However if as additional contraints you have projection number from two other particular directions then the solution is unique and can be computed in polynomial time as shown by Alain Daurat [2 and 8] .

References

[1]
M. Chrobak, P. Couperus, C. Dürr, Gerhard Woeginger, 'A Note on Tiling under Tomographic Constraints', [references]
[2]
C. Dürr, Flavio Guiñez, Martín Matamala, 'Reconstructing 3-colored grids from horizontal and vertical projections is NP-hard', [references]
[3]
C. Dürr, E. Goles, I. Rapaport, E. Rémila, 'Tiling with bars under tomographic constraints', [references]
[4]
R.J. Gardner; P. Gritzmann; D. Prangenberg, 'On the computational complexity of reconstructing polyatomic structures from their X-rays', Theoretical Computer Science, 1998.
[5]
H.J. Ryser, 'Combinatorial Mathematics' , Mathematical Association of America and Quinn & Boden, Rahway, New Jersey, 1963. (Observation on linear implementation )
[6]
C. Picouleau, Reconstruction of domino tiling from its two orthogonal projections, Theoretical Computer Science, 255:437-447, 2001.