Cylindrical algebraic decomposition II

an adjacency algorithm for the plane

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

*Corresponding author for this work

Research output: Contribution to journalArticle

72 Citations (Scopus)

Abstract

Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space Epartitions Er 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 cads 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. The authors give here in Part II an algorithm which determines the pairs of adjacent cells as it constructs a cad of E2.

Original languageEnglish
Pages (from-to)878-889
Number of pages12
JournalSIAM Journal on Computing
Volume13
Issue number4
DOIs
Publication statusPublished - 1 Jan 1984
Externally publishedYes

Keywords

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

Fingerprint Dive into the research topics of 'Cylindrical algebraic decomposition II: an adjacency algorithm for the plane'. Together they form a unique fingerprint.

  • Cite this