A cluster-based cylindrical algebraic decomposition algorithm

Let A ⊂ Z [x1,000, xr be a finite set. An A-invariant cylindrical algebraic decomposition (cad) is a certain partitlon of r-dlmensional euclidean space Er into semi-algebralc cells such that the value of each Ai ∈ A has constant sign (positive, negative, or zero) throug|umt each cell. Two cells are adjacent if their union is connected. Recently a number of mathoda have been given for augmenting Colllns' cad construction algorithm (1975), so that in addition to specifying the cell~ that comprise a cad, it identifies the pairs of adjacent cells. Assuming the availability of such an adjacency algorithm, in this paper we give a modified cad construction algorithm based on the utillzatloa of clusters of cells in a cad (a cluster is a collection of cells whose union is connected). Preliminary observations indicate that the 11ew algorithm can be significantly more efficient in some cases than the original, although in other examples it is somewhat less efficient