<$ $f_{i+1}(a)$. A ‘cylinder’ over a region $R$ is the set of all points $(a,b)$, where $a \in R$ and $b \in \mathbb{R}$. A ‘stack’ over a region $R$ is the collection of sections and sectors that occur in the cylinder over $R$. A partition of $\mathbb{R}^{n}$ into semialgebraic partitions is called an ‘algebraic decomposition’ of $\mathbb{R}^{n}$.

An algebraic partition of $\mathbb{R}^{n}$ satisfying the following two properties is called a ‘cylindrical algebraic decomposition’:

1.  If $n=1$, then the CAD is a set of points and open intervals.

2.  If $n>1$, every region of the CAD of $\mathbb{R}^{n-1}$ has a stack over it, which is a disjoint subset of the CAD of $\mathbb{R}^{n}$.

A set of polynomials, $F$ is said to be ‘sign invariant’ on the region $R$ iff no polynomial in $F$ changes its sign anywhere on $R$.

A CAD $C$ of $\mathbb{R}^n$ is sign invariant with respect to a set of polynomials, $P$ if and only if $P$ is sign invariant on every cell of $C$.

The algorithm to generate the CAD of $\mathbb{R}^{n}$(which shall be referred to as ‘CAD Algorithm’) has two phases of execution, namely projection and construction. Projection is specified by a projection operator, whereas construction 