6.4 Computational Algebraic Geometry

This section presents algorithms that are so general that they solve any problem of Formulation 4.1 and even the closed-chain problems of Section 4.4. It is amazing that such algorithms exist; however, it is also unfortunate that they are both extremely challenging to implement and not efficient enough for most applications. The concepts and tools of this section were mostly developed in the context of computational real algebraic geometry [77,250]. They are powerful enough to conquer numerous problems in robotics, computer vision, geometric modeling, computer-aided design, and geometric theorem proving. One of these problems happens to be motion planning, for which the connection to computational algebraic geometry was first recognized in [852].

- 6.4.1 Basic Definitions and Concepts
- Tarski sentences
- The decision problem
- The quantifier-elimination problem
- Semi-algebraic decomposition

- 6.4.2 Cylindrical Algebraic Decomposition
- Semi-algebraic projections are semi-algebraic
- Real algebraic numbers
- One-dimensional decomposition
- The inductive step to higher dimensions
- Solving a motion planning problem

- 6.4.3 Canny's Roadmap Algorithm

Steven M LaValle 2012-04-20