20. – 24. Januar 1997, Dagstuhl-Seminar 97042

Discrete Tomography: Algorithms and Complexity


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

Auskunft zu diesem Dagstuhl-Seminar erteilt

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 der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.