Divide and conquer roadmap for algebraic sets

Abstract. Let R be a real closed field, and D ⊂ R an ordered domain. We describe an algorithm that given as input a polynomial P ∈ D[X1,..., Xk], and a finite set, A = {p1,..., pm}, of points contained in V = Zer(P, Rk) described by real univariate representations, computes a roadmap of V containing A. The complexity of the algorithm, measured by the number of arithmeti