January 20 – 24 , 1997, Dagstuhl Seminar 97042

Discrete Tomography: Algorithms and Complexity


P. Gritzmann (Trier), M. Nivat (Paris)

For support, please contact

Dagstuhl Service Team


Dagstuhl-Seminar-Report 165


The workshop, organized by P. Gritzmann (Trier), and M. Nivat (Paris), was attended by 20 participants from 5 countries (7 nationalities). It was a workshop in the very sense of the word, without a fixed formal schedule, many of the talks were spontaneous and informal presentations at the black board, and the discussion of ideas and new approaches in discrete tomography was central.

The basic problem of discrete tomography is to reconstruct finite point sets that are accessable only through some of their discrete X-rays. In the simplest case, an X-ray of a finite set F in a direction u is a function giving the number of its points on each line parallel to u, effectively the projection, counted with multiplicity, of F on the subspace orthogonal to u.

The continuous analogue of this reconstruction problem is the classical task to invert X-ray or Radon-transformations, a problem of fundamental importance in computerized tomography. While the continuous problem is quite well understood (and the solution techniques are utilized in practise so prominently), the problem changes dramatically when turning to the discrete case. Questions of discrete tomography have long been studied in the context of image processing and data compression, and in the realm of data security; new motivation, however, comes from the need of practical reconstuction techniques in material sciences.

The talks discussed a broad range of aspects of discrete tomography. Some focussed on the real-world aspects of discrete tomography, others presented theoretical structural insight, partly with a view towards comparing discrete and continuous tomography. Some talks dealt with the computational complexity of various tasks relevant in this area while others focussed on algorithmic approaches using deterministic techniques from computer algebra or polyhedral combinatorics aiming at optimal solutions or randomized algorithms aiming at good approximations. Yet other presentations rounded of the area by giving insight in its connection to other problems and explaining related problems and results.

The workshop brought together scientists of various fields and with different scientific background. By way of exchanging ideas and problems, discussing possible approaches usually until late at night, presenting existing software and discussing encouraging new ideas and directions of possible further progress the workshop made a significant contribution to the solution of the important underlying real-world problems.


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.