SIAM Journal on Computing · 1984 · 132 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryGeometric ModelingCell DecompositionGeometry ProcessingAdjacency RelationsCell Adjacency GraphsDecompositions
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. Informally, two cells of a cad are adjacent if they touch each other; formally, they are adjacent if their union is connected. In applications of cad’s one often wishes to know the adjacent pairs of cells. Previous algorithms for cad construction (such as that given in Part I of this paper) have not actually determined them. We give here in Part II an algorithm which determines the pairs of adjacent cells as it constructs a cad of $E^2 $.
6
On Euclid's Algorithm and the Theory of Subresultants
Warren S. Brown, J. F. Traub · Journal of the ACM · 1971 · 258 citations · Full text
Homology and cohomology theory
Gian‐Carlo Rota · Advances in Mathematics · 1978 · 107 citations
A note on simplification orderings
Nachum Dershowitz · Information Processing Letters · 1979 · 93 citations