As stated previously, the sequence of projections ends with a univariate polynomial over . 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 in a complex in for 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 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 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
are used, instead of the more general
. The field
is not *algebraically
closed* because zeros of the
polynomials lie outside of
. For example, if
, then for
, and
.
However, some elements of
can never be roots of a polynomial in
.

The set
of all real roots to all polynomials in
is
called the set of *real algebraic numbers*. The set
actually represents a field (recall from Section
4.4.1). Several nice algorithmic properties of the
numbers in
are 1) they all have finite representations, 2)
addition and multiplication operations on elements of
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, , can be used by choosing 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
, in
which is the degree of the polynomial [852]. See
[77,173,852] for detailed presentations on the
exact representation and calculation with real algebraic numbers.

Steven M LaValle 2012-04-20