Cylindrical algebraic decomposition is also capable of solving any of the motion planning problems formulated in Chapter 4. First assume that . As for other decompositions, a roadmap is formed in which every vertex is an -cell and edges connect every pair of adjacent -cells by traveling through an -cell. It is straightforward to determine adjacencies inside of a cylinder, but there are several technical details associated with determining adjacencies of cells from different cylinders (pages 152-154 of [77] present an example that illustrates the problem). The cells of dimension less than are not needed for motion planning purposes (just as vertices were not needed for the vertical decomposition in Section 6.2.2). The query points and are connected to the roadmap depending on the cell in which they lie, and a discrete search is performed.

If
and its dimension is for , then all
of the interesting cells are of lower dimension. This occurs, for
example, due to the constraints on the matrices to force them to lie
in or . This may also occur for problems from Section
4.4, in which closed chains reduce the degrees of
freedom. The cylindrical algebraic decomposition method can still
solve such problems; however, the exact root representation problem
becomes more complicated when determining the cell adjacencies. A
discussion of these issues appears in [852]. For the case
of and , this complication can be avoided by using
*stereographic projection* to map
or
to
or
, respectively. This mapping removes a single point from each,
but the connectivity of
remains unharmed. The antipodal
identification problem for unit quaternions represented by
also
does not present a problem; there is a redundant copy of , which
does not affect the connectivity.

The running time for cylindrical algebraic decomposition depends on many factors, but in general it is polynomial in the number of polynomials in , polynomial in the maximum algebraic degree of the polynomials, and doubly exponential in the dimension. Complexity issues are covered in more detail in Section 6.5.3.

Steven M LaValle 2012-04-20