One-dimensional decomposition

To explain the cylindrical algebraic decomposition method, we first perform a semi-algebraic decomposition of $ {\mathbb{R}}$, which is the final step in the projection sequence. Once this is explained, then the multi-dimensional case follows more easily.

Let $ {\cal F}$ be a set of $ m$ univariate polynomials,

$\displaystyle {\cal F}= \{ f_i \in {\mathbb{Q}}[x] \; \vert \; i = 1, \ldots, m\} ,$ (6.18)

which are used to define some semi-algebraic set in $ {\mathbb{R}}$. The polynomials in $ {\cal F}$ could come directly from a quantifier-free formula $ \phi $ (which could even appear inside of a Tarski sentence, as in (6.9)).

Define a single polynomial as $ f = \prod_{i=1}^m f_i$. Suppose that $ f$ has $ k$ distinct, real roots, which are sorted in increasing order:

$\displaystyle -\infty \; < \; {\beta}_1 \; < \; {\beta}_2 \; < \; \cdots \; < \...
...beta}_i \; < \; {\beta}_{i+1} \; < \; \cdots \; < \; {\beta}_k \; < \; \infty .$ (6.19)

The one-dimensional semi-algebraic decomposition is given by the following sequence of alternating $ 1$-cells and 0-cells:

\begin{displaymath}\begin{split}&(-\infty,{\beta}_1), \; [{\beta}_1,{\beta}_1], ...
...s, \; [{\beta}_k,{\beta}_k], \; ({\beta}_k,\infty). \end{split}\end{displaymath} (6.20)

Any semi-algebraic set that can be expressed using the polynomials in $ {\cal F}$ can also be expressed as the union of some of the 0-cells and $ 1$-cells given in (6.20). This can also be considered as a singular complex (it can even be considered as a simplicial complex, but this does not extend to higher dimensions).

Sample points can be generated for each of the cells as follows. For the unbounded cells $ [-\infty,{\beta}_1)$ and $ ({\beta}_k,\infty]$, valid samples are $ {\beta}_1 - 1$ and $ {\beta}_k + 1$, respectively. For each finite $ 1$-cell, $ ({\beta}_i,{\beta}_{i+1})$, the midpoint $ ({\beta}_i+{\beta}_{i+1})/2$ produces a sample point. For each 0-cell, $ [{\beta}_i,{\beta}_i]$, the only choice is to use $ {\beta}_i$ as the sample point.

Figure 6.31: Two parabolas are used to define the semi-algebraic set $ [1,2]$.
\begin{figure}\centerline{\psfig{file=figs/parabolas.eps,width=4.5in}}\end{figure}

Figure 6.32: A semi-algebraic decomposition for the polynomials in Figure 6.31.
\begin{figure}\centerline{\psfig{file=figs/parabolas2.eps,width=4.5truein}}\end{figure}

Example 6..5 (One-Dimensional Decomposition)   Figure 6.31 shows a semi-algebraic subset of $ {\mathbb{R}}$ that is defined by two polynomials, $ f_1(x) = x^2 - 2x$ and $ f_2(x) = x^2 -
4x + 3$. Here, $ {\cal F}= \{f_1,f_2\}$. Consider the quantifier-free formula

$\displaystyle \phi (x) = (x^2 - 2x \geq 0) \wedge (x^2 - 4x + 3 \geq 0) .$ (6.21)

The semi-algebraic decomposition into five $ 1$-cells and four 0-cells is shown in Figure 6.32. Each cell is sign invariant. The sample points for the $ 1$-cells are $ -1$, $ 1/2$, $ 3/2$, $ 5/2$, and $ 4$, respectively. The sample points for the 0-cells are 0, $ 1$, $ 2$, and $ 3$, respectively.

A decision problem can be nicely solved using the decomposition. Suppose a Tarski sentence that uses the polynomials in $ {\cal F}$ has been given. Here is one possibility:

$\displaystyle \Phi = \exists x [(x^2 - 2x \geq 0) \wedge (x^2 - 4x + 3 \geq 0)]$ (6.22)

The sample points alone are sufficient to determine whether $ \Phi $ is TRUE or FALSE. Once $ x=1$ is attempted, it is discovered that $ \Phi $ is TRUE. The quantifier-elimination problem cannot yet be considered because more dimensions are needed. $ \blacksquare$

Steven M LaValle 2020-08-14