Algebraic methods for non-linear computational geometry (invited address)

In this lecture we present a survey on three algebraic algorithmic methods for problems in algebraic geometry: Characteristic Sets (Ritt, Wu), Gröbner Bases (Buchberger), and Cylindrical Algebraic Decomposition (Collins).

There are at least three reasons why algebraic methods seem to be promising for the future of geometric reasoning. First, in advanced geometric reasoning applications, the consideration of global properties of (quite complicated) non-linear objects is indispensible. These considerations, so far, were not in the scope of “traditional” computational geometry in the sense of (Preparata, Shamos 1985) or (Edelsbrunner 1987), where the emphasis is almost exclusively on combinatorial properties of linear (or very simple non-linear) objects. Second, some advanced geometric problems need the exact representation of objects as opposed to numerical approximation. For example, curve tracing in the neighborhood of singularities needs algebraic considerations that go beyond evaluation of points. Third, the automation of high-level geometric design processes, for example the conversion of parametric to implicit representations of geometric objects, needs symbolic computation involving parameters (variables, indeterminates). Algebra is the natural framework for this type of geometric computation.

In fact, (real and complex) algebraic geometry, by its very nature, should be the natural mathematical setting for geometric reasoning by algebraic techniques. However, strangely enough, mainstream algebraic geometry was totally inconstructive in the last six decades and most of the constructive techniques of the nineteenth-century algebraic geometry are available only in examples rather than in terms of general algorithms. For the immediate future, however, we envisage a research impulse towards algorithmic algebraic geometry turning the fascinating insights of inconstructive algebraic geometry into algorithmic methods for geometric reasoning. We also expect that a closer contact between “traditional computational geometry”, as reflected by the ACM Computational Geometry Symposia, and computer algebra should result in exciting new techniques.

The three techniques covered in this survey evolved in the past two decades. They solve problems of increasing generality and scope of applicability. Roughly, Characteristic Sets allow to detect whether or not a polynomial is in the radical of a polynomial ideal, Gröbner Bases solve the canonical simplification problem for polynomial congruences, and Cylindrical Algebraic Decomposition finds a complete set of sample points for the cells of the Euclidean space in which a set of polynomials is sign-invariant.

Based on these fundamental properties of the three methods, a large number of problems in real and complex algebraic geometry can be solved algorithmically, for example, decomposition and global analysis of algebraic varieties, geometrical theorem proving, solution of diophantine polynomial equations, implicitization of parametric variety representations, quantifier-free representation of sets described by formulae in the theory of real-closed fields and many others. The solvability of these problems has immediate applications for important geometric engineering problems as, for example, robot collision detection, robot path finding, inverse kinematics for dynamic systems, consistency analysis in computer-aided design, curve tracing, construction of blending surfaces and others.

The practical applicability of these algebraic methods is limited by their intrinsic complexity. Much research is conducted aiming at improvements of the methods for special classes of input. Also, these methods should be seen in a preprocessing context.

Roughly, the content of this lecture is identical to the survey (Buchberger, Collins, Kutzler 1988). The best survey on the method of characteristic sets is still (Wu 1984). Two surveys on Gröbner Bases with details about the algorithms and the applications are (Buchberger 1985) and (Buchberger 1988). (Arnon, Collins, McCallum 1984) is a systematic presentation of Collins' method including some improvements of the method. A collection of new original papers on Collins' Cylindrical Algebraic Decomposition method and related topics is (Arnon, Buchberger 1988). This collection contains also an extensive bibliography on the field. The original papers in which the three methods were introduced are (Ritt 1950) and (Wu 1984) (Characteristic Sets), (Buchberger 1965, 1970) (Gröbner Bases) and (Collins 1975) (Cylindrical Algebraic Decomposition).