Now consider constructing a cylindrical algebraic decomposition for (note the decomposition is actually semi-algebraic). Figure 6.35 shows an example for . First consider how to iteratively project the polynomials down to to ensure that when the decomposition of is constructed, the sign-invariant property is maintained. The resulting decomposition corresponds to a singular complex.

There are two cases that cause cell boundaries to be formed, as
shown in Figure 6.33. Let
denote the
original set of polynomials in
that are used to
define the semi-algebraic set (or Tarski sentence) in
. Form a
single polynomial
. Let
, which is also a polynomial. Let
, which is the greatest common divisor of and
. The set of zeros of is the set of all points that are
zeros of both and . Being a zero of means
that the surface given by does not vary locally when perturbing
. These are places where a cell boundary needs to be formed
because the surface may fold over itself in the direction, which
is not permitted for a cylindrical decomposition. Another place where
a cell boundary needs to be formed is at the intersection of two or
more polynomials in
. The projection technique from
to
generates a set,
, of polynomials in
that satisfies these requirements. The
polynomials
have the property that at least one
contains a zero point below every point in
for which
and
, or polynomials in
intersect. The projection method that constructs
involves computing *principle subresultant coefficients*, which
are covered in [77,853]. Resultants, of which the
subresultants are an extension, are covered in [250].

The polynomials in are then projected to to obtain . This process continues until is obtained, which is a set of polynomials in . A one-dimensional decomposition is formed, as defined earlier. From , a single polynomial is formed by taking the product, and is partitioned into 0-cells and -cells. We next describe the process of lifting a decomposition over up to . This technique is applied iteratively until is reached.

Assume inductively that a cylindrical algebraic decomposition has been
computed for a set of polynomials
in
. The decomposition consists of -cells for
which
. Let
. For each one of the -cells , a
*cylinder* over is defined
as the -dimensional set

(6.23) |

The cylinder is sliced into a strip of -dimensional and -dimensional cells by using polynomials in . Let denote one of the slicing polynomials in the cylinder, sorted in increasing order as , , , , , , . The following kinds of cells are produced (see Figure 6.34):

**Lower unbounded sector:**and (6.24)

**Section:**and (6.25)

**Bounded sector:**and (6.26)

**Upper unbounded sector:**and (6.27)

Note that the cells do not necessarily project onto a rectangular set, as in the case of a higher dimensional vertical decomposition. For example, a generic -cell for a decomposition of is described as the open set of such that

- $&bull#bullet;$
- for some 0-cells , which are roots of some .
- $&bull#bullet;$
- lies between and for some -cells , , which are zeros of some .
- $&bull#bullet;$
- lies between and for some -cells , , which are zeros of some .
- $&bull#bullet;$
- lies between and for some -cells , , which are zeros of some .

The resulting decomposition is sign invariant, which allows the decision and quantifier-elimination problems to be solved in finite time. To solve a decision problem, the polynomials in are evaluated at every sample point to determine whether one of them satisfies the Tarski sentence. To solve the quantifier-elimination problem, note that any semi-algebraic sets that can be constructed from can be defined as a union of some cells in the decomposition. For the given Tarski sentence, is formed from all polynomials that are mentioned in the sentence, and the cell decomposition is performed. Once obtained, the sign information is used to determine which cells need to be included in the union. The resulting union of cells is designed to include only the points in at which the Tarski sentence is TRUE.

Steven M LaValle 2012-04-20