On Approximations and Incidence in Cylindrical Algebraic Decompositions
Author:
- David PrillDPDavid Prill
- 1 November 1986
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (4) , 972-993
Abstract
Let $P \subset \mathbb{Z}[x_1 , \cdots ,x_r ]$ be a finite set. This paper describes and analyzes a variant of the algorithm of Collins and others for decomposing $\mathbb{R}^r $ into semi-algebraic cells so that the value of each $f \in P$ has constant sign (positive, negative, or zero) on the points of each cell. The version here has several advantages: 1. The boundary of each cell is a disjoint union of lower-dimensional cells. For each bounded cell $\alpha $ the pair $(\bar \alpha ,\alpha )$ is homeomorphic to a closed ball and its interior. 2. An algorithm is presented which for fixed r computes incidence of cells in polynomial time. 3. A priori estimates of the accuracy of approximations of roots of polynomials required in order to determine the combinatorial structure of the cell complex are given. This avoids computation in algebraic number fields.
Keywords
This publication has 13 references indexed in Scilit:
- Cylindrical Algebraic Decomposition II: An Adjacency Algorithm for the PlaneSIAM Journal on Computing, 1984
- On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifoldsAdvances in Applied Mathematics, 1983
- The fastest exact algorithms for the isolation of the real roots of a polynomial equationComputing, 1980
- Quantifier elimination for real closed fields by cylindrical algebraic decompostion1975
- Triangulations of algebraic sets1975
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common DivisorsJournal of the ACM, 1971
- Subresultants and Reduced Polynomial Remainder SequencesJournal of the ACM, 1967
- Sur L'Homologie des Varietes Algebriques Réelles1965
- Simpliziale Zerlegung abz hlbarer analytischer R umeMathematische Zeitschrift, 1964
- On the covering of analytic loci by complexesTransactions of the American Mathematical Society, 1932