Cylindrical algebraic decomposition I: the basic algorithm

Dennis S. Arnon; George E. Collins; Scott McCallum

doi:10.1137/0213054

Cylindrical algebraic decomposition I: the basic algorithm

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

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

50 Citations (Scopus)

Abstract

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. 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 E². 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 language	English
Pages (from-to)	865-877
Number of pages	13
Journal	SIAM Journal on Computing
Volume	13
Issue number	4
DOIs	https://doi.org/10.1137/0213054
Publication status	Published - 1 Jan 1984
Externally published	Yes

Keywords

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

Access to Document

10.1137/0213054

Cite this

@article{2eefc3ab269f4a978541cd9ff4af37da,

title = "Cylindrical algebraic decomposition I: the basic algorithm",

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.",

keywords = "polynomial zeros, computer algebra, computational geometry, semi-algebraic geometry, real closed fields, decision procedures, real algebraic geometry",

author = "Arnon, {Dennis S.} and Collins, {George E.} and Scott McCallum",

year = "1984",

month = jan,

day = "1",

doi = "10.1137/0213054",

language = "English",

volume = "13",

pages = "865--877",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics",

number = "4",

}

TY - JOUR

T1 - Cylindrical algebraic decomposition I

T2 - the basic algorithm

AU - Arnon, Dennis S.

AU - Collins, George E.

AU - McCallum, Scott

PY - 1984/1/1

Y1 - 1984/1/1

N2 - 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.

AB - 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.

KW - polynomial zeros

KW - computer algebra

KW - computational geometry

KW - semi-algebraic geometry

KW - real closed fields

KW - decision procedures

KW - real algebraic geometry

UR - http://www.scopus.com/inward/record.url?scp=0021521367&partnerID=8YFLogxK

U2 - 10.1137/0213054

DO - 10.1137/0213054

M3 - Article

AN - SCOPUS:0021521367

SN - 0097-5397

VL - 13

SP - 865

EP - 877

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -

Cylindrical algebraic decomposition I: the basic algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this