## 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 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 .

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 , and after one projection, a semi-algebraic set is obtained in . Eventually, the projection reaches , 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 -cells (intervals) and 0-cells is formed by partitioning . The sequence is then reversed, and decompositions are formed from up to . Each iteration starts with a cell decomposition in and lifts it to obtain a cylinder of cells in . Figure 6.35 shows how the decomposition looks for the gingerbread example; since , it only involves one projection and one lifting.

Subsections
Steven M LaValle 2012-04-20