#### The inductive step to higher dimensions

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):
1. Lower unbounded sector:

 and (6.24)

2. Section:

 and (6.25)

3. Bounded sector:

 and (6.26)

4. Upper unbounded sector:

 and (6.27)

There is one degenerate possibility in which there are no slicing polynomials and the cylinder over can be extended into one unbounded cell. In general, the sample points are computed by picking a point in and making a vertical column of samples of the form . A polynomial in can be generated, and the samples are placed using the same assignment technique that was used for the one-dimensional decomposition.

Example 6..6 (Mutilating the Gingerbread Face)   Figure 6.35 shows a cylindrical algebraic decomposition of the gingerbread face. Observe that the resulting complex is very similar to that obtained in Figure 6.19.

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