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

International audienceLet R be a real closed field and D ⊂ R an ordered domain. We give an algorithm that takes as input a polynomial Q ∈ D[X 1 , . . . , X k ], and computes a description of a roadmap of the set of zeros, Zer(Q, R k), of Q in R k . The complexity of the algorithm, measured by the number of arithmetic opera-tions in the ordered domain D, is bounded by d O(k √ k) , where d = deg(Q) ≥ 2. As a consequence, there exist algorithms for computing the number of semi-algebraically connected components of a real algebraic set, Zer(Q, R k), whose complexity is also bounded by d O(k √ k) , where d = deg(Q) ≥ 2. The best pre-viously known algorithm for constructing a roadmap of a real algebraic subset of R k defined by a polynomial of degree d has complexity d O(k 2)