Cylindrical Algebraic Decomposition I: The Basic Algorithm
Dennis S. Arnon, George E. Collins, Scott McCallum · SIAM Journal on Computing · 1984
Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space $E^r $ partitions $E^r $ into connected subsets compatible with the zeros of the polynomials. Each subset is a cell Collins gave a cad construction algorithm in 1975, as part of a quantifier elimination procedure for real closed fields. The cad algorithm has found diverse applications (optimization, curve display); new applications have been proposed (term rewriting systems, motion planning). In the present two-part paper, we give an algorithm which determines the pairs of adjacent cells as it constructs a cad of $E^2 $. Such information is often useful in applications. In Part I we describe the essential features of the r-space cad algorithm, to provide a framework for the adjacency algorithm in Part II.
Cited by 344 works. doi:10.1137/0213054
Authors
References
- On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifolds
- Equations and Rewrite Rules: A Survey
- Topologische Begründung des Kalküls der abzählenden Geometrie
- On Euclid's Algorithm and the Theory of Subresultants
- Quantifier elimination for real closed fields by cylindrical algebraic decompostion
- Quantifier Elimination for Real Closed Fields by Cylindrical Algebraic Decomposition
- Generalized Polynomial Remainder Sequences
- The Computational Complexity of Logical Theories
- A note on simplification orderings
- Computing in Algebraic Extensions