Computational Real Algebraic Geometry

Abstract

Computational real algebraic geometry studies various algorithmic questions dealing with the real solutions of a system of equalities, inequalities, and inequations of polynomials over the real numbers. This emerging field is largely motivated by the power and elegance with which it solves a broad and general class of problems arising in robotics, vision, computer aided design, geometric theorem proving, etc. The algorithmic problems that arise in this context are formulated as decision problems for the first-order theory of reals and the related problems of quantifier elimination (Section 1). The associated geometric structures are then examined via an exploration of the semi-algebraic sets (Section 2). Algorithmic problems for semi-algebraic sets are considered next. In particular, there is a discussion of real algebraic numbers and their representation which relies on such classical theorems as Stu