Cylindrical algebraic decomposition I

the basic algorithm

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

*Corresponding author for this work

Research output: Contribution to journalArticle

183 Citations (Scopus)

Abstract

Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space Er partitions Er into connected subsets compatible with the zeros of the polynomials. Each subset is a cell. G. E. Collins gave a cad construction algorithm in 1975, as part of a quantifier elimination procedure for real closed fields. The cad algorithm has found diverse applications (optimization, curve display); new applications have been proposed (term rewriting systems, motion planning). In the present two-part paper, the authors give an algorithm which determines the pairs of adjacent cells as it constructs a cad of E2. Such information is often useful in applications. In Part I they describe the essential features of the r-space cad algorithm, to provide a framework for the adjacency algorithm in Part II.

Original languageEnglish
Pages (from-to)865-877
Number of pages13
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 I: the basic algorithm'. Together they form a unique fingerprint.

Cite this