Cylindrical algebraic decomposition

In mathematics, cylindrical algebraic decomposition (CAD) is a notion and an algorithm to compute it, which are fundamental for computer algebra and real algebraic geometry. Given a set S of polynomials in R, a cylindrical algebraic decomposition is a decomposition of R into connected semialgebraic sets called cells, on which each polynomial has constant sign, either +, − or 0. For being cylindrical, this decomposition must satisfy the following condition: If 1 ≤ k < n and π is the projection from R onto R consisting in removing the k last coordinates, then for every cells c and d, one has either π(c) = π(d) or π(c) ∩ π(d) = ∅. This implies that the images by π of the cells define a cylindrical decomposition of R.