An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space

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

doi:10.1007/3-540-15984-3_272

An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space

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

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

4 Citations (Scopus)

Abstract

Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space E^r is a certain partition of E^r into connected subsets compatible with the zeros of the polynomials. Each subset is a cell. Two cells of a cad are adjacent if their union is connected. In applications of cad's, one often wishes to know the pairs of adjacent cells. In a previous paper we gave an algorithm which determines the adjacent cells as it constructs a cad of the plane. We give such an algorithm here for three-dimensional space.

Original language	English
Title of host publication	EUROCAL 1985 - European Conference on Computer Algebra, Proceedings
Editors	Bob F. Caviness
Publisher	Springer-VDI-Verlag GmbH & Co. KG
Pages	246-261
Number of pages	16
ISBN (Print)	9783540159841
DOIs	https://doi.org/10.1007/3-540-15984-3_272
Publication status	Published - 1 Jan 1985
Externally published	Yes
Event	European Conference on Computer Algebra, EUROCAL 1985 - Linz, Austria Duration: 1 Apr 1985 → 3 Apr 1985

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	204 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	European Conference on Computer Algebra, EUROCAL 1985
Country	Austria
City	Linz
Period	1/04/85 → 3/04/85

Access to Document

10.1007/3-540-15984-3_272

Link to publication in Scopus

Fingerprint Dive into the research topics of 'An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space'. Together they form a unique fingerprint.

Cite this

Arnon, D. S., Collins, G. E., & McCallum, S. (1985). An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space. In B. F. Caviness (Ed.), EUROCAL 1985 - European Conference on Computer Algebra, Proceedings (pp. 246-261). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 204 LNCS). Springer-VDI-Verlag GmbH & Co. KG. https://doi.org/10.1007/3-540-15984-3_272

Arnon, Dennis S. ; Collins, George E. ; McCallum, Scott. / An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space. EUROCAL 1985 - European Conference on Computer Algebra, Proceedings. editor / Bob F. Caviness. Springer-VDI-Verlag GmbH & Co. KG, 1985. pp. 246-261 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3594f0e994bf41efa57ca2e949c636bc,

title = "An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space",

abstract = "Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space Er is a certain partition of Er into connected subsets compatible with the zeros of the polynomials. Each subset is a cell. Two cells of a cad are adjacent if their union is connected. In applications of cad's, one often wishes to know the pairs of adjacent cells. In a previous paper we gave an algorithm which determines the adjacent cells as it constructs a cad of the plane. We give such an algorithm here for three-dimensional space.",

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

year = "1985",

month = "1",

day = "1",

doi = "10.1007/3-540-15984-3_272",

language = "English",

isbn = "9783540159841",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-VDI-Verlag GmbH & Co. KG",

pages = "246--261",

editor = "Caviness, {Bob F.}",

booktitle = "EUROCAL 1985 - European Conference on Computer Algebra, Proceedings",

address = "Germany",

}

Arnon, DS, Collins, GE & McCallum, S 1985, An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space. in BF Caviness (ed.), EUROCAL 1985 - European Conference on Computer Algebra, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 204 LNCS, Springer-VDI-Verlag GmbH & Co. KG, pp. 246-261, European Conference on Computer Algebra, EUROCAL 1985, Linz, Austria, 1/04/85. https://doi.org/10.1007/3-540-15984-3_272

An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space. / Arnon, Dennis S.; Collins, George E.; McCallum, Scott.

EUROCAL 1985 - European Conference on Computer Algebra, Proceedings. ed. / Bob F. Caviness. Springer-VDI-Verlag GmbH & Co. KG, 1985. p. 246-261 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 204 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution

TY - GEN

T1 - An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space

AU - Arnon, Dennis S.

AU - Collins, George E.

AU - McCallum, Scott

PY - 1985/1/1

Y1 - 1985/1/1

N2 - Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space Er is a certain partition of Er into connected subsets compatible with the zeros of the polynomials. Each subset is a cell. Two cells of a cad are adjacent if their union is connected. In applications of cad's, one often wishes to know the pairs of adjacent cells. In a previous paper we gave an algorithm which determines the adjacent cells as it constructs a cad of the plane. We give such an algorithm here for three-dimensional space.

AB - Given a set of r-variate integral polynomials, a cylindrical algebraic decomposition (cad) of euclidean r-space Er is a certain partition of Er into connected subsets compatible with the zeros of the polynomials. Each subset is a cell. Two cells of a cad are adjacent if their union is connected. In applications of cad's, one often wishes to know the pairs of adjacent cells. In a previous paper we gave an algorithm which determines the adjacent cells as it constructs a cad of the plane. We give such an algorithm here for three-dimensional space.

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

U2 - 10.1007/3-540-15984-3_272

DO - 10.1007/3-540-15984-3_272

M3 - Conference proceeding contribution

SN - 9783540159841

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 246

EP - 261

BT - EUROCAL 1985 - European Conference on Computer Algebra, Proceedings

A2 - Caviness, Bob F.

PB - Springer-VDI-Verlag GmbH & Co. KG

ER -

Arnon DS, Collins GE, McCallum S. An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space. In Caviness BF, editor, EUROCAL 1985 - European Conference on Computer Algebra, Proceedings. Springer-VDI-Verlag GmbH & Co. KG. 1985. p. 246-261. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-15984-3_272