Semi-algebraic decomposition

As stated in Section 6.3.1, motion planning inside of each cell in a complex should be trivial. To solve the decision and quantifier-elimination problems, a cell decomposition was developed for which these problems become trivial in each cell. The decomposition is designed so that only a single point in each cell needs to be checked to solve the decision problem.

The semi-algebraic set $Y \subseteq {\mathbb{R}}^n$ that is expressed with (6.15) is

$$Y = \bigcup_{i=1}^k \; \bigcap_{j=1}^{m_i} \left\{ (x_1,\ldots, x... ...athbb{R}}^n \; \vert \; {\rm sgn}(f_{i,j}(x_1,\ldots, x_n)) = s_{i,j} \right\},$$ (6.16)

in which ${\rm sgn}$ is the sign function, and each $s_{i,j} \in \{-1,0,1\}$, which is the range of ${\rm sgn}$. Once again the nice relationship between set-theory and logic, which was described in Section 3.1, appears here. We convert from a set-theoretic description to a logical predicate by changing $\cup$ and $\cap$ to $\vee$ and $\wedge$, respectively.

Let ${\cal F}$ denote the set of $m = \sum_{i=1}^k m_i$ polynomials that appear in (6.16). A sign assignment with respect to ${\cal F}$ is a vector-valued function, ${\rm sgn}_{\cal F}: {\mathbb{R}}^n \rightarrow \{-1,0,1\}^m$. Each $f \in {\cal F}$ has a corresponding position in the sign assignment vector. At this position, the sign, ${\rm sgn}(f(x_1,\ldots, x_n)) \in \{-1,0,1\}$, appears. A semi-algebraic decomposition is a partition of ${\mathbb{R}}^n$ into a finite set of connected regions that are each sign invariant. This means that inside of each region, ${\rm sgn}_{\cal F}$ must remain constant. The regions will not be called cells because a semi-algebraic decomposition is not necessarily a singular complex as defined in Section 6.3.1; the regions here may contain holes.

Figure 6.30: A semi-algebraic decomposition of the gingerbread face yields $9$ sign-invariant regions.

Example 6..4 (Sign assignment)   Recall Example 3.1 and Figure 3.4 from Section 3.1.2. Figure 3.4a shows a sign assignment for a case in which there is only one polynomial, ${\cal F}= \{x^2 + y^2 - 4\}$. The sign assignment is defined as

$${\rm sgn}_{\cal F}(x,y) = \left\{ \begin{array}{ll} -1 & \mbox{ i... ...+ y^2 - 4 = 0$ } 1 & \mbox{ if $x^2 + y^2 - 4 > 0$. } \end{array}\right.$$ (6.17)

Now consider the sign assignment ${\rm sgn}_{\cal F}$, shown in Figure 6.30 for the gingerbread face of Figure 3.4b. The polynomials of the semi-algebraic model are ${\cal F}= \{f_1,f_2,f_3,f_4\}$, as defined in Example 3.1. In order, these are the ``head,'' ``left eye,'' ``right eye,'' and ``mouth.'' The sign assignment produces a four-dimensional vector of signs. Note that if $(x,y)$ lies on one of the zeros of a polynomial in ${\cal F}$, then a 0 appears in the sign assignment. If the curves of two or more of the polynomials had intersected, then the sign assignment would produce more than one 0 at the intersection points.

For the semi-algebraic decomposition for the gingerbread face in Figure 6.30, there are nine regions. Five 2D regions correspond to: 1) being outside of the face, 2)inside of the left eye, 3) inside of the right eye, 4) inside of the mouth, and 5) inside of the face but outside of the mouth and eyes. There are four 1D regions, each of which corresponds to points that lie on one of the zero sets of a polynomial. The resulting decomposition is not a singular complex because the $(-1,1,1,1)$ region contains three holes. $\blacksquare$

A decomposition such as the one in Figure 6.30 would not be very useful for motion planning because of the holes in the regions. Further refinement is needed for motion planning, which is fortunately produced by cylindrical algebraic decomposition. On the other hand, any semi-algebraic decomposition is quite useful for solving the decision problem. Only one point needs to be checked inside of each region to determine whether some Tarski sentence that has no free variables is true. Why? If the polynomial signs cannot change over some region, then the TRUE/FALSE value of the corresponding logical predicate, $\Phi$, cannot change. Therefore, it sufficient only to check one point per sign-invariant region.