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 proceedingConference proceeding contribution

4 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationEUROCAL 1985 - European Conference on Computer Algebra, Proceedings
EditorsBob F. Caviness
PublisherSpringer-VDI-Verlag GmbH & Co. KG
Pages246-261
Number of pages16
ISBN (Print)9783540159841
DOIs
Publication statusPublished - 1 Jan 1985
Externally publishedYes
EventEuropean Conference on Computer Algebra, EUROCAL 1985 - Linz, Austria
Duration: 1 Apr 19853 Apr 1985

Publication series

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

Conference

ConferenceEuropean Conference on Computer Algebra, EUROCAL 1985
CountryAustria
CityLinz
Period1/04/853/04/85

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