Computational Synthetic Geometry
Bernd Sturmfels · Medical Entomology and Zoology · 1989
Computational synthetic geometry aims to develop algorithms to find for a given abstract geometric object either a coordinatization over some field or a proof that such a realization does not exist. Several important realizability problems, mainly from convexity and incidence geometry, can be reduced to matroids and oriented matroids. Our presentation emphasizes these structures, with the understanding that many techniques apply to more general problems. In Chapter II we prove that, roughly speaking, realizability algorithms for a field K exist if and only if there is a decision procedure for integer polynomial equations over K. For the rationals this implies the equivalence of the unsolved rational version of Hilbert's 10th problem with certain diophantine problems in combinatorial geometry. Chapter III deals with specific combinatorial and algebraic methods for our realizability problems. An algorithm based on Grasmann algebra is developed and applied to various rank 3 matroids. In particular, we classify all algebraic varieties corresponding to 10$\sb{3}$-configurations. We also study inequality reductions for oriented matroids and we discuss in detail one realizable and one non-realizable case. These latter results are partly due to J. Bokowski, D. Ljubic, J. P. Roudneff and J. Richter. Chapter IV gives a self-contained exposition of the (semi-)algebraic geometry of (oriented) matroids. We develop the theory of final polynomials as a systematic approach to prove non-realizability. In view of his earlier results J. Bokowski asked whether a final polynomial exists in every non-realizable case. We give an affirmative answer to this question and we present many old and new examples from geometry. After completion of our research we learned that similar results follow also from the earlier unpublished work of A. Dress. We resolve a problem of N. White on weak maps and specialization of coordinates in matroid theory by relating our approach to the recent work of I. M. Gelfand et.al. on the matroid stratification of complex Grasmann varieties. In Chapter V we discuss geometric methods for the realization of oriented matroids and polytopes which are related to the study of the topology of the respective realization spaces. Finally, we suggest an integral geometric approach to oriented matroids based on the Haar probability measure on Grasmannians.