A Baby Step-Giant Step Roadmap Algorithm for General Algebraic Sets

Let be a real closed field and an ordered domain. We present an algorithm that takes as input a polynomial and computes a description of a roadmap of the set of zeros, of Q in The complexity of the algorithm, measured by the number of arithmetic operations in the ordered domain is bounded by where As a consequence, there exist algorithms for computing the number of semialgebraically connected components of a real algebraic set, whose complexity is also bounded by where The best previously known algorithm for constructing a roadmap of a real algebraic subset of defined by a polynomial of degree d has complexity.