## Abstract

Let A ₂ Z [x_{1}, ..., x_{r}] be a finite set. An A-invariant cylindrical algebraic decomposition (cad) is a certain partition of r-dimenslonal euclidean space E^{r} into semi-algebraic cells such that the value of each A_{i} ∈ A has constant sign (positive, negative, or zero) throughout each cell. Two cells are adjacent if their union is connected. We give an algorithm that determines the adjacent pairs of cells as it constructs a cad of E^{3}. The general teehnlque employed for E^{3} adjacency determination is “projection” into E^{2}, followed by application of an existing E^{2} adjacency elgorlthm (Arnon, Collins, McCallum, 1984). Our algorithm has the following properties: (1) it requires no coordinate changes, end (2) in any cad of E^{1}, E^{2}, or E^{3} that it builds, the boundary of each cell is a (disjoint) union of lower-dlmenaionel cells.

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

Pages (from-to) | 163-187 |

Number of pages | 25 |

Journal | Journal of Symbolic Computation |

Volume | 5 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 1 Jan 1988 |

Externally published | Yes |