Cylindrical algebraic decomposition. I: The basic algorithm. II: An adjacency algorithm for the plane. (English) Zbl 0562.14001

Given a set of r-variate integral polynomials, a cylindrical algebraic (cad) decomposition of the Euclidean r-space \(E^ r\) is a partition of \(E^ r\) into connected subsets (cells) compatible with the zeros of the polynomials. Two cells of a cad are adjacent if they touch each other. - The aim of this two-part paper is to give (in part I) a cad construction algorithm and then to present (here, in part II) an algorithm which determines the pairs of adjacent cells.
Reviewer: I.Mihuţ


14-04 Software, source code, etc. for problems pertaining to algebraic geometry
14Pxx Real algebraic and real-analytic geometry
12D10 Polynomials in real and complex fields: location of zeros (algebraic theorems)
68W99 Algorithms in computer science
Full Text: DOI