Computing roadmaps of semi-algebraic sets on a variety
Saugata Basu, Richard M. Pollack, Marie-Françoise Roy · Journal of the American Mathematical Society · 1999
We consider a semi-algebraic set S S defined by s s polynomials in k k variables which is contained in an algebraic variety Z ( Q ) Z(Q) . The variety is assumed to have real dimension k ′ , k’, the polynomial Q Q and the polynomials defining S S have degree at most d d . We present an algorithm which constructs a roadmap on S S . The complexity of this algorithm is s k ′ + 1 d O ( k 2 ) s^{k’+1}d^{O(k^2)} . We also present an algorithm which, given a point of S 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 τ O ( 1 ) d O ( k 2 ) .