Computing Roadmaps of General Semi-Algebraic Sets

In this paper we study the problem of determining whether two points lie in the same connected component of a semi-algebraic set S. Although we are mostly concerned with sets S ⊆ Rk, our algorithm can also decide if points in an arbitrary set S ⊆ Rk can be joined by joined by a semi-algebraic path, for any real closed field R. Our algorithm computes a one-dimensional semi-algebraic subset R(S) of S (actually of an embedding of S in a space Rk for a certain real extension field R of the given field R. R(S) is called the roadmap of S. The basis of this work is the roadmap algorithm described in [3,4] which worked only for compact, regularly stratified sets.