Solving Polynomial Strict Inequalities Using Cylindrical Algebraic Decomposition

S MCCALLUM*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We consider the problem of determining the consistency over the real numbers of a system of integral polynomial strict inequalities. This problem has applications in geometric modelling. The cylindrical algebraic decomposition (cad) algorithm [2] can be used to solve this problem, though not very efficiently. In this paper we present a less powerful version of the cad algorithm which can be used to solve the consistency problem for conjunctions of strict inequalities, and which runs considerably faster than the original method applied to this problem. In the case that a given conjunction of strict inequalities is consistent, the modified cad algorithm constructs solution points with rational coordinates.

Original languageEnglish
Pages (from-to)432-438
Number of pages7
JournalComputer Journal
Volume36
Issue number5
DOIs
Publication statusPublished - 1993

Cite this