Algorithms for the geometry of semi-algebraic sets
Dennis S. Arnon · Minds at UW (University of Wisconsin) · 1981
Let A be a set of polynomials in r variables with integer coefficients. An A-invariant cylindrical algebraic decomposition (cad) of r-dimensional Euclidean space (G. Collins, Lect. Notes Comp. Sci., 33, Springer-Verlag, 1975, pp 134-183) is a certain cellular decomposition of r-space, such that each cell is a semi-algebraic set, the polynomials of A are sign-invariant on each cell, and the cells are arranged into cylinders. The cad algorithm given by Collins provides, among other applications, the fastest known decision procedure for real closed fields, a cellular decomposition algorithm for semi-algebraic sets, and a method of solving nonlinear (polynomial) optimization problems exactly. The time-consuming calculations with real algebraic numbers required by the algorithm have been an obstacle to its implementation and use. The major contribution of this thesis is a new version of the cad algorithm for r (LESSTHEQ) 3, in which one works with maximal connected A-invariant collections of cells, in such a way as to often avoid the most time-consuming algebraic number calculations. Essential to this new cad algorithm is an algorithm we present for determination of adjacenies among the cells of a cad. Computer programs for the cad and adjacency algorithms have been written, providing the first complete implementation of a cad algorithm. Empirical data obtained from application of these programs are presented and analyzed.