An adjacency algorithm for cylindrical algebraic decompositions of three-dimenslonal space

Dennis S. Arnon*, George E. Collins, Scott McCallum

*Corresponding author for this work

Research output: Contribution to journalArticle

24 Citations (Scopus)

Abstract

Let A ₂ Z [x1, ..., xr] be a finite set. An A-invariant cylindrical algebraic decomposition (cad) is a certain partition of r-dimenslonal euclidean space Er into semi-algebraic cells such that the value of each Ai ∈ 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 E3. The general teehnlque employed for E3 adjacency determination is “projection” into E2, followed by application of an existing E2 adjacency elgorlthm (Arnon, Collins, McCallum, 1984). Our algorithm has the following properties: (1) it requires no coordinate changes, end (2) in any cad of E1, E2, or E3 that it builds, the boundary of each cell is a (disjoint) union of lower-dlmenaionel cells.

Original languageEnglish
Pages (from-to)163-187
Number of pages25
JournalJournal of Symbolic Computation
Volume5
Issue number1-2
DOIs
Publication statusPublished - 1 Jan 1988
Externally publishedYes

Fingerprint Dive into the research topics of 'An adjacency algorithm for cylindrical algebraic decompositions of three-dimenslonal space'. Together they form a unique fingerprint.

  • Cite this