On Approximations and Incidence in Cylindrical Algebraic Decompositions
David Prill · SIAM Journal on Computing · 1986
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.