Axiomatic Discrete Geometry

Axiomatic Discrete Geometry
Nils Anders Danielsson
Master's thesis, Imperial College of Science, Technology and Medicine, London, 2002. [pdf, ps.gz, errata (errors listed have been corrected in the online version)]

Abstract

The main approaches to image analysis and manipulation, computational geometry, and related fields are based on continuous geometry. This easily leads to trouble with rounding errors and algorithms that return erroneous output, or even fail to terminate gracefully. In view of this we can argue that the proper framework for many algorithms is not continuous, but discrete. Furthermore it is preferable if such a framework is axiomatically defined, so that the essential properties of the system are clearly stated and many models can share the same theory.

In this report we analyse Hübler's axiomatic discrete geometry, one of the few of its kind—perhaps the only one. The system is characterised in terms of torsion free Z-modules satisfying some so-called generator properties. The new axiomatisation obtained is arguably easier to understand than the original one, and the work casts new light on different properties of Hübler's geometries. His system turns out to be too restricted for our purposes, but the results indicate some ways in which to continue this thread of work.

In the process of doing the characterisation of Hübler's system it is shown that all modules over integral domains have a natural (possibly infinite) matroid structure. This was already known, but not well-known, and in this text some of the consequences are examined. Furthermore it is shown how to define a natural oriented matroid structure over all modules over ordered domains, and all torsion free modules over ordered domains are shown to be antimatroids under a certain closure operator. Convexity is examined in relation to both oriented matroids and antimatroids.

Stolfi's oriented projective geometry, which is used in practice, is also treated in the text. The goal is to find a good axiomatisation of oriented projective geometry that has useful discrete models. Two axiomatisations, both in terms of infinite modular oriented matroids, are proposed. It is shown that Stolfi's geometries are models of one of the systems. This part of the report should even more than the rest be seen as a starting point for further investigations.