6.4.2 Cylindrical Algebraic Decomposition

Cylindrical algebraic decomposition is a general method that produces a cylindrical decomposition in the same sense considered in Section 6.3.2 for polygons in ${\mathbb{R}}^2$ and also the decomposition in Section 6.3.4 for the line-segment robot. It is also referred to as Collins decomposition after its original developer [40,232,233]. The decomposition in Figure 6.19 can even be considered as a cylindrical algebraic decomposition for a semi-algebraic set in which every geometric primitive is a linear polynomial. In this section, such a decomposition is generalized to any semi-algebraic set in ${\mathbb{R}}^n$.

The idea is to develop a sequence of projections that drops the dimension of the semi-algebraic set by one each time. Initially, the set is defined over ${\mathbb{R}}^n$, and after one projection, a semi-algebraic set is obtained in ${\mathbb{R}}^{n-1}$. Eventually, the projection reaches ${\mathbb{R}}$, and a univariate polynomial is obtained for which the zeros are at the critical places where cell boundaries need to be formed. A cell decomposition of $1$-cells (intervals) and 0-cells is formed by partitioning ${\mathbb{R}}$. The sequence is then reversed, and decompositions are formed from ${\mathbb{R}}^2$ up to ${\mathbb{R}}^n$. Each iteration starts with a cell decomposition in ${\mathbb{R}}^i$ and lifts it to obtain a cylinder of cells in ${\mathbb{R}}^{i+1}$. Figure 6.35 shows how the decomposition looks for the gingerbread example; since $n=2$, it only involves one projection and one lifting.