Cylindrical algebraic decomposition

Given a set S of polynomials in Rⁿ, the Cylindrical algebraic decomposition algorithm finds a decomposition of Rⁿ into cells on which each polynomial has constant sign. This decomposition is cylindrical in the following sense: If 1≤k<n and π is the projection from Rⁿ onto R^n-k consisting in removing the k last coordinates, then for every cells c and d, one has either π(c) = π(d) or π(c) ∩ π(d) = ∅.

This algorithm, introduced by Georges E. Collins in 1975 gives an effective version of Tarski's real quantifier elimination and Tarski-Seidenberg theorem, which is efficient enough for being implemented on a computer. It is one of the most important algorithms of computational real algebraic geometry.

References

• Basu, Saugata; Pollack, Richard; Roy, Marie-Françoise Algorithms in real algebraic geometry. Second edition. Algorithms and Computation in Mathematics, 10. Springer-Verlag, Berlin, 2006. x+662 pp. ISBN: 978-3-540-33098-1; 3-540-33098-4
• Strzebonski, Adam. Cylindrical Algebraic Decomposition from MathWorld.
• Cylindrical Algebraic Decomposition in Planning algorithms by Steven M. LaValle. Accessed 13 July 2007