** Next:** Projection
** Up:** An overview of quantifier
** Previous:** Some conventions and notation

##

What is a CAD?

An * algebraic decomposition*
is one in which each cell is a semi-algebraic set. A * cylindrical
algebraic decomposition* is an algebraic decomposition with a special
structure.
Any algebraic decomposition of into open intervals and
single points is a CAD. So a CAD of 1-space consists of cells
, where the are algebraic numbers.
Obviously, cells in a CAD of have the natural ordering
.

Let be a connected region in . A * stack*
over is a decomposition of
into
cells
such that for any
the intersection of the with
forms a CAD of with the natural ordering that the
cell defined by
is less than the
cell defined by
if and only if . Thus, the cells in a stack have a natural ordering just like a
CAD of . The even-indexed cells are real-valued
functions defined on , since their intersection with
is always a single point. They are called *
sections*. The odd-indexed cells are * sectors*. In a stack
defined by an algebraic decomposition of
,
each section is part of the zero set of some -level polynomial.
If the natural algebraic decomposition of
defined by a given set of polynomials is a stack over , the
set of polynomials is said to be * delineable* over .

An algebraic decomposition is a CAD of
provided
that:

- There exists a CAD of
, call it , such that for any
cell there exists a cell such that the
projection onto
of is . is the
*
induced CAD* of
.
- For cell in the induced CAD of
, the cells
in whose projections onto
are form a stack over
.

The cells in the stack over are called the * children* of
, and is called their * parent*.

** Next:** Projection
** Up:** An overview of quantifier
** Previous:** Some conventions and notation
*Christopher W Brown*

*2001-07-10*