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

Arnon, Dennis S.; Collins, George E.; McCallum, Scott

SIAM J. Comput. 13, 865-877, 878-889 (1984).

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

Keywords:

computational geometry; decision procedure; real algebraic geometry; cylindrical algebraic decomposition of the Euclidean r-space; cad; zeros of the polynomials; algorithm; pairs of adjacent cells