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:

1. 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 .
2. 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