Real algebraic numbers

As stated previously, the sequence of projections ends with a univariate polynomial over ${\mathbb{R}}$. The sides of the cells will be defined based on the precise location of the roots of this polynomial. Furthermore, representing a sample point for a cell of dimension $k$ in a complex in ${\mathbb{R}}^n$ for $k < n$ requires perfect precision. If the coordinates are slightly off, the point will lie in a different cell. This raises the complicated issue of how these roots are represented and manipulated in a computer.

For univariate polynomials of degree $4$ or less, formulas exist to compute all of the roots in terms of functions of square roots and higher order roots. From Galois theory [469,769], it is known that such formulas and nice expressions for roots do not exist for most higher degree polynomials, which can certainly arise in the complicated semi-algebraic models that are derived in motion planning. The roots in ${\mathbb{R}}$ could be any real number, and many real numbers require infinite representations.

One way of avoiding this mess is to assume that only polynomials in ${\mathbb{Q}}[x_1,\ldots, x_n]$ are used, instead of the more general ${\mathbb{R}}[x_1,\ldots, x_n]$. The field ${\mathbb{Q}}$ is not algebraically closed because zeros of the polynomials lie outside of ${\mathbb{Q}}^n$. For example, if $f(x_1) = x_1^2 - 2$, then $f = 0$ for $x_1 = \pm \sqrt{2}$, and $\sqrt{2} \not \in {\mathbb{Q}}$. However, some elements of ${\mathbb{R}}$ can never be roots of a polynomial in ${\mathbb{Q}}[x_1,\ldots, x_n]$.

The set ${\mathbb{A}}$ of all real roots to all polynomials in ${\mathbb{Q}}[x]$ is called the set of real algebraic numbers. The set ${\mathbb{A}}\subset {\mathbb{R}}$ actually represents a field (recall from Section 4.4.1). Several nice algorithmic properties of the numbers in ${\mathbb{A}}$ are 1) they all have finite representations, 2) addition and multiplication operations on elements of ${\mathbb{A}}$ can be computed in polynomial time, and 3) conversions between different representations of real algebraic numbers can be performed in polynomial time. This means that all operations can be computed efficiently without resorting to some kind of numerical approximation. In some applications, such approximations are fine; however, for algebraic decompositions, they destroy critical information by potentially confusing roots (e.g., how can we know for sure whether a polynomial has a double root or just two roots that are very close together?).

The details are not presented here, but there are several methods for representing real algebraic numbers and the corresponding algorithms for manipulating them efficiently. The running time of cylindrical algebraic decomposition ultimately depends on this representation. In practice, a numerical root-finding method that has a precision parameter, $\epsilon$, can be used by choosing $\epsilon$ small enough to ensure that roots will not be confused. A sufficiently small value can be determined by applying gap theorems, which give lower bounds on the amount of real root separation, expressed in terms of the polynomial coefficients [173]. Some methods avoid requiring a precision parameter. One well-known example is the derivation of a Sturm sequence of polynomials based on the given polynomial. The polynomials in the Sturm sequence are then used to find isolating intervals for each of the roots [77]. The polynomial, together with its isolating interval, can be considered as an exact root representation. Algebraic operations can even be performed using this representation in time $O(d \lg^2 d)$, in which $d$ is the degree of the polynomial [852]. See [77,173,852] for detailed presentations on the exact representation and calculation with real algebraic numbers.