TY - JOUR
T1 - An adjacency algorithm for cylindrical algebraic decompositions of three-dimenslonal space
AU - Arnon, Dennis S.
AU - Collins, George E.
AU - McCallum, Scott
PY - 1988/1/1
Y1 - 1988/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0001092841&partnerID=8YFLogxK
U2 - 10.1016/S0747-7171(88)80011-7
DO - 10.1016/S0747-7171(88)80011-7
M3 - Article
AN - SCOPUS:0001092841
SN - 0747-7171
VL - 5
SP - 163
EP - 187
JO - Journal of Symbolic Computation
JF - Journal of Symbolic Computation
IS - 1-2
ER -