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 $\mathbb {R}^1$ into open intervals and single points is a CAD. So a CAD of 1-space consists of cells $c_1 = (-\infty,\alpha_1),c_2 = [\alpha_1,\alpha_1],c_3 = (\alpha_1,\alpha_2), \ldots , c_{2m} = [\alpha_m,\alpha_m], c_{2m+1} = (\alpha_m,\infty)$, where the $\alpha_i$ are algebraic numbers. Obviously, cells in a CAD of $\mathbb {R}^1$ have the natural ordering $c_1 < c_2 < \cdots < c_{2m+1}$.

Let $\cal A$ be a connected region in $\mathbb {R}^i$. A stack over $\cal A$ is a decomposition of ${\cal A} \times \mathbb {R}$ into cells $c_1, \ldots ,c_{2m+1}$ such that for any $\alpha \in {\cal A}$ the intersection of the $c_i$ with $\alpha \times \mathbb {R}$ forms a CAD of $\mathbb {R}^1$ with the natural ordering that the cell defined by $c_i \cap (\alpha \times \mathbb {R})$ is less than the cell defined by $c_j \cap (\alpha \times \mathbb {R})$ if and only if $i < j$. Thus, the cells in a stack have a natural ordering just like a CAD of $\mathbb {R}^1$. The even-indexed cells are real-valued functions defined on ${\cal A}$, since their intersection with $\alpha \times \mathbb {R}$ is always a single point. They are called sections. The odd-indexed cells are sectors. In a stack defined by an algebraic decomposition of ${\cal A} \times \mathbb {R}$, each section is part of the zero set of some $(i+1)$-level polynomial. If the natural algebraic decomposition of ${\cal A} \times \mathbb {R}$ defined by a given set of polynomials is a stack over ${\cal A}$, the set of polynomials is said to be delineable over ${\cal A}$.

An algebraic decomposition $D$ is a CAD of $\mathbb {R}^{i+1}$ provided that:

1. There exists a CAD of $\mathbb {R}^{i}$, call it $D'$, such that for any cell $c \in D$ there exists a cell $c' \in D'$ such that the projection onto $\mathbb {R}^{i}$ of $c$ is $c'$. $D'$ is the induced CAD of $\mathbb {R}^{i}$.
2. For cell $c'$ in the induced CAD of $\mathbb {R}^{i}$, the cells in $D$ whose projections onto $\mathbb {R}^{i}$ are $c'$ form a stack over $c'$.

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