TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 97042

Discrete Tomography: Algorithms and Complexity

( Jan 20 – Jan 24, 1997 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/97042

Organizers
  • M. Nivat (Paris)
  • P. Gritzmann (Trier)



Summary

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.

Copyright

Participants
  • M. Nivat (Paris)
  • P. Gritzmann (Trier)