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
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Within this website:
External resources:
Within this website:
External resources:
  • the dblp Computer Science Bibliography

Dagstuhl Seminar 02221

Mathematical Structures for Computable Topology and Geometry

( May 26 – May 31, 2002 )

Please use the following short url to reference this page:




Topological notions and methods have successfully been applied in various areas of computer science. Computerized geometrical constructions have many applications in engineering. The seminar will concentrate on mathematical structures underlying both computable topology and geometry.

Due to the digital nature of most applications in computer science these structures have to be different from the mathematical structures which are classically used in applications of topology and geometry in physics and engineering and which are based on the continuum. The new areas of digital topology and digital geometry take into account that in computer applications we have to deal with discrete sets of pixels.

A further aspect in which topological structures used in computer science differ from the classical ones is partiality. Classical spaces contain only the ideal elements that are the result of a computation (approximation) process. Since we want to reason on such processes in a formal (automated) way the structures also have to contain the partial (and finite) objects appearing during a computation. Only these finite objects can be observed in finite time.

At least three types of computationally convenient structures for topology have been studied, and all of them may be developed in the direction of geometry. The first is domains, the second locales (and formal topology), and the third cell complexes.

Domain theory provides interesting possibilities for exact infinitary computation (apart from the applications to programming language semantics for which it was originally developed). There are the "maximal point models": the interval domain in which the real numbers are embedded as maximal elements is an example of this. Escardó has used it for his development of a programming language that allows computing with intervals. More recently we have seen domain models for convexity, with intended applications in computer-aided design.

Closely related to domain theory is the theory of locales, and its logical counterpart: formal topology . Here, one takes a constructive attitude and starts from the already mentioned fact that only the finitely describable properties of the ideal mathematical entities we are interested in are observable. Thus, these properties are the primary object of study. The ideal entities are obtained as derived objects.

In geometry a similar approach tries to develop a system suitable for "commonsense" spatial reasoning, by taking regions rather than points as the basic entities. Developed initially by philosophers under the name mereology (and later, mereotopology), this viewpoint has been taken up by researchers interested in applications in AI, robotics, and GIS. Despite the obvious analogy with point-free topology (as above), there has been relatively little interaction so far.

The region-based theories have typically had the infinite divisibility of space built in; attempts at a discrete version are few. Here one may expect that cell complex theory in which, after all, the cells are usually thought of as convex regions could help. Cell complexes have, indeed, long played a part in image processing. These cell complexes may be either "concrete" (derived explicitly from Euclidean space, or more generally from a manifold), or "abstract". The concrete complexes do not provide us with the autonomous theory we are looking for; the abstract complexes permit the computation of various topological invariants, but do not support specifically geometric features such as convexity and linearity. To make progress, it seems that we need either to endow the abstract complexes with suitable extra structure, or else to ground them in some richer combinatorial structures (not classical manifolds).

A candidate for such a "richer combinatorial structure" is: the oriented matroid. Despite pioneering work by Knuth (1991), these have been somewhat neglected by computer scientists. It seems likely that oriented matroid theory will have a significant input to the (eventual) foundations of digital geometry, even if this has been little recognized so far.

It is the aim of the seminar to bring together people working in fields like domain theory, computer science oriented topology and geometry, formal topology,... and to foster interaction between them. Moreover, we want to encourage communication and, hopefully, collaboration between computer scientists and those mathematicians who work on similar problems but from a different perspective and who, often, are not aware of the computer science motivations.

  • Laura Anderson (SUNY - Binghamton, US)
  • Ulrich Berger (Swansea University, GB) [dblp]
  • Jürgen Bokowski (TU Darmstadt, DE)
  • Vasco Brattka (University of Cape Town, ZA) [dblp]
  • Lawrence M. Brown (Hacettepe University - Ankara, TR)
  • Mark H. Burstein (BBN Technologies - Cambridge, US)
  • Giovanni Curi (University of Padova, IT)
  • Martín H. Escardó (University of Birmingham, GB) [dblp]
  • Robin Forman (Rice University, US)
  • Chyi-Jou Gau (CUNY-Queens College - Flushing, US)
  • Silvia Gebellato (University of Padova, IT)
  • Christopher Gilmour (University of Cape Town, ZA)
  • Reinhold Heckmann (AbsInt - Saarbrücken, DE) [dblp]
  • Peter Hertling (Universität der Bundeswehr - München, DE) [dblp]
  • Pascal Hitzler (KIT - Karlsruher Institut für Technologie, DE) [dblp]
  • Achim Jung (University of Birmingham, GB) [dblp]
  • Klaus Keimel (TU Darmstadt, DE) [dblp]
  • Yukiko Kenmochi (Okayama University, JP)
  • Gisela Klette (University of Auckland, NZ) [dblp]
  • Reinhard Klette (University of Auckland, NZ) [dblp]
  • Ralph Kopperman (City University of New York, US)
  • Hans-Peter Albert Künzi (University of Cape Town, ZA) [dblp]
  • Jimmie D. Lawson (Louisiana State University - Baton Rouge, US) [dblp]
  • Serguei Matveev (Chelyabinsk State University, RU)
  • Michael W. Mislove (Tulane University, US) [dblp]
  • M. Andrew Moshier (Chapman University - Orange, US) [dblp]
  • Maria O'Keeffe (University College Cork, IE)
  • Thomas J. Peters (University of Connecticut - Storrs, US)
  • John L. Pfaltz (University of Virginia - Charlottesville, US)
  • Jörg Rambau (Universität Bayreuth, DE)
  • Martin Raussen (Aalborg University, DK) [dblp]
  • Ingrid Rewitzky (University of Cape Town, ZA)
  • Tom Richmond (Western Kentucky Univ. - Bowling Green, US)
  • Anthony Roy (University of Leeds, GB)
  • Giovanni Sambin (University of Padova, IT)
  • Francisco Santos (University of Cantabria, ES) [dblp]
  • Anneliese Schauerte (University of Cape Town, ZA)
  • Michel P. Schellekens (University College Cork, IE)
  • Markus Schneider (University of Florida - Gainesville, US)
  • Matthias Schröder (University of Edinburgh, GB) [dblp]
  • Peter M. Schuster (LMU München, DE) [dblp]
  • Alex Simpson (University of Edinburgh, GB) [dblp]
  • Michael B. Smyth (Imperial College London, GB)
  • Dieter Spreen (Universität Siegen, DE) [dblp]
  • John Stell (University of Leeds, GB)
  • Rueiher Tsaur (Imperial College London, GB)
  • Hideki Tsuiki (Kyoto University, JP)
  • Peter Veelaert (Hogent - Ghent, BE)
  • Steven J. Vickers (University of Birmingham, GB) [dblp]
  • Luminita Simona Vita (University of Canterbury - Christchurch, NZ)
  • Guojun Wang (Shaanxi Normal University - Xi'an, CN)
  • Pawel Waszkiewicz (Jagiellonian University - Kraków, PL)
  • Julian Webster (Imperial College London, GB)
  • Klaus Weihrauch (FernUniversität in Hagen, DE) [dblp]
  • Petra Wiederhold de Matos (CINVESTAV - Mexico, MX)
  • Richard G. Wilson (Universidad Nacional Autonoma - Mexico, MX)
  • Guo-Qiang Zhang (Case Western Reserve University - Cleveland, US)