zbMATH — the first resource for mathematics

Computational synthetic geometry. (English) Zbl 0683.05015
Lecture Notes in Mathematics, 1355. Berlin etc.: Springer-Verlag. 168 p. DM 30.00 (1989).
Computational geometry is a rapidly growing young field on the edge of mathematics and computer science. The authors’ research monograph Computational synthetic geometry is a fascinating contribution to this new field. Computational synthetic geometry focusses on algorithmic aspects of certain fundamental realizability problems in discrete geometry and convexity. Typical examples include the construction of polytopes from simplicial complexes, vector geometries from incidence structures, and hyperplane arrangements from oriented matroids. The authors show that algorithms for these constructions exist if and only if arbitrary polynomial equations are decidable over the underlying field. This leads to many new insights on polytopes, projective configurations and combinatorics of Grassmann varieties. Particularly impressive is the discussion of the Steinitz problem for convex polytopes. At the same time the approach involves the study and development of techniques from computational algebraic geometry, convexity and automated theorem proving.
This book is highly recommended to anyone who is interested or working in discrete or computational geometry. It is very likely that it will stimulate further research in this area.
Reviewer: E.Schulte

05B35 Combinatorial aspects of matroids and geometric lattices
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
14M15 Grassmannians, Schubert varieties, flag manifolds
51A20 Configuration theorems in linear incidence geometry
52Bxx Polytopes and polyhedra
68W30 Symbolic computation and algebraic computation
51D20 Combinatorial geometries and geometric closure systems
68R99 Discrete mathematics in relation to computer science
Full Text: DOI