Cylindrical algebraic decomposition II: an adjacency algorithm for the plane

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

doi:10.1137/0213055

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 journal › Article › peer-review

75 Citations (Scopus)

Abstract

Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space E^rpartitions 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 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 E².

Original language	English
Pages (from-to)	878-889
Number of pages	12
Journal	SIAM Journal on Computing
Volume	13
Issue number	4
DOIs	https://doi.org/10.1137/0213055
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/0213055

Cite this

@article{c6d3a4561814437088291de7809ac92a,

title = "Cylindrical algebraic decomposition II: an adjacency algorithm for the plane",

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

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/0213055",

language = "English",

volume = "13",

pages = "878--889",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics",

number = "4",

}

TY - JOUR

T1 - Cylindrical algebraic decomposition II

T2 - an adjacency algorithm for the plane

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

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

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=0021522643&partnerID=8YFLogxK

U2 - 10.1137/0213055

DO - 10.1137/0213055

M3 - Article

AN - SCOPUS:0021522643

VL - 13

SP - 878

EP - 889

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 4

ER -

Cylindrical algebraic decomposition II: an adjacency algorithm for the plane

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this