26. – 31. Mai 2002, Dagstuhl Seminar 02221
Mathematical Structures for Computable Topology and Geometry
Auskunft zu diesem Dagstuhl Seminar erteilt
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.