6.4.1 Basic Definitions and Concepts

This section builds on the semi-algebraic model definitions from Section 3.1 and the polynomial definitions from Section 4.4.1. It will be assumed that ${\cal C}\subseteq {\mathbb{R}}^n$, which could for example arise by representing each copy of $SO(2)$ or $SO(3)$ in its $2 \times 2$ or $3 \times 3$ matrix form. For example, in the case of a 3D rigid body, we know that ${\cal C}= {\mathbb{R}}^3 \times {\mathbb{RP}}^3$, which is a six-dimensional manifold, but it can be embedded in ${\mathbb{R}}^{12}$, which is obtained from the Cartesian product of ${\mathbb{R}}^3$ and the set of all $3 \times 3$ matrices. The constraints that force the matrices to lie in $SO(2)$ or $SO(3)$ are polynomials, and they can therefore be added to the semi-algebraic models of ${\cal C}_{obs}$ and ${\cal C}_{free}$. If the dimension of ${\cal C}$ is less than $n$, then the algorithm presented below is sufficient, but there are some representation and complexity issues that motivate using a special parameterization of ${\cal C}$ to make both dimensions the same while altering the topology of ${\cal C}$ to become homeomorphic to ${\mathbb{R}}^n$. This is discussed briefly in Section 6.4.2.

Suppose that the models in ${\mathbb{R}}^n$ are all expressed using polynomials from ${\mathbb{Q}}[x_1,\ldots, x_n]$, the set of polynomials^6.6 over the field of rational numbers ${\mathbb{Q}}$. Let $f \in {\mathbb{Q}}[x_1,\ldots, x_n]$ denote a polynomial.