Computing roadmaps of semi-algebraic sets on a variety

We consider a semi-algebraic set $S$ defined by $s$ polynomials in $k$ variables which is contained in an algebraic variety $Z(Q)$. The variety is assumed to have real dimension $k',$ the polynomial $Q$ and the polynomials defining $S$ have degree at most $d$. We present an algorithm which constructs a roadmap on $S$. The complexity of this algorithm is $s^{k'+1}d^{O(k^2)}$. We also present an algorithm which, given a point of $S$ defined by polynomials of degree at most $\tau$, constructs a path joining this point to the roadmap. The complexity of this algorithm is $k' s \tau^{O(1)} d^{O(k^2)}.$ These algorithms easily yield an algorithm which, given two points of $S$ defined by polynomials of degree at most $\tau$, decides whether or not these two points of $S$ lie in the same semi-algebraically connected component of $S$ and if they do computes a semi-algebraic path in $S$ connecting the two points.