Algebraic cell decomposition in NC
- 1 January 1985
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 515-521
- https://doi.org/10.1109/sfcs.1985.4
Abstract
We give an algorithm to construct a cell decomposition of Rd, including adjacency information, defined by any given set of rational polynomials in d variables. The algorithm runs in single exponential parallel time, and in NC for fixed d. The algorithm extends a recent algorithm of Ben-Or, Kozen, and Reif for deciding the theory of real closed fields.Keywords
This publication has 12 references indexed in Scilit:
- Cylindrical Algebraic Decomposition II: An Adjacency Algorithm for the PlaneSIAM Journal on Computing, 1984
- Cylindrical Algebraic Decomposition I: The Basic AlgorithmSIAM Journal on Computing, 1984
- The complexity of elementary algebra and geometryPublished by Association for Computing Machinery (ACM) ,1984
- Geometric retrieval problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Constructing arrangements of lines and hyperplanes with applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- On the “piano movers” problem. II. General techniques for computing topological properties of real algebraic manifoldsAdvances in Applied Mathematics, 1983
- Topologically reliable display of algebraic curvesACM SIGGRAPH Computer Graphics, 1983
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- On Euclid's Algorithm and the Theory of SubresultantsJournal of the ACM, 1971