Local box adjacency algorithms for cylindrical algebraic decompositions

Scott McCallum*, George E. Collins

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


We describe new algorithms for determining the adjacencies between zero-dimensional cells and those one-dimensional cells that are sections (not sectors) in cylindrical algebraic decompositions (cad). Such adjacencies constitute a basis for determining all other cell adjacencies. Our new algorithms are local, being applicable to a specified OD cell and the 1D cells described by specified polynomials. Particularly efficient algorithms are given for the OD cells in spaces of dimensions two, three and four. Then an algorithm is given for a space of arbitrary dimension. This algorithm may on occasion report failure, but it can then be repeated with a modified isolating interval and a likelihood of success.

Original languageEnglish
Pages (from-to)321-342
Number of pages22
JournalJournal of Symbolic Computation
Issue number3
Publication statusPublished - 2002


Dive into the research topics of 'Local box adjacency algorithms for cylindrical algebraic decompositions'. Together they form a unique fingerprint.

Cite this