## Abstract

Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space E^{r} partitions E^{r} into connected subsets compatible with the zeros of the polynomials. Each subset is a cell. G. E. Collins gave a cad construction algorithm in 1975, as part of a quantifier elimination procedure for real closed fields. The cad algorithm has found diverse applications (optimization, curve display); new applications have been proposed (term rewriting systems, motion planning). In the present two-part paper, the authors give an algorithm which determines the pairs of adjacent cells as it constructs a cad of E^{2}. Such information is often useful in applications. In Part I they describe the essential features of the r-space cad algorithm, to provide a framework for the adjacency algorithm in Part II.

Original language | English |
---|---|

Pages (from-to) | 865-877 |

Number of pages | 13 |

Journal | SIAM Journal on Computing |

Volume | 13 |

Issue number | 4 |

DOIs | |

Publication status | Published - 1 Jan 1984 |

Externally published | Yes |

## Keywords

- polynomial zeros
- computer algebra
- computational geometry
- semi-algebraic geometry
- real closed fields
- decision procedures
- real algebraic geometry