# zbMATH — the first resource for mathematics

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ţ

##### MSC:
 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: