We study the problem of answering connectivity queries on real solution sets of polynomial systems, a central question in computational real algebraic geometry with applications ranging from geometry to robotics. Following Canny’s roadmap framework, connectivity queries on a high-dimensional solution set are reduced to connectivity queries on a one-dimensional algebraic curve intersecting all connected components.
We present an algorithm that, under generic assumptions, computes such roadmaps in subquadratic time with respect to the output size, thereby extending the best known nearly optimal complexity bounds to non-compact situations. We also show that the connectivity of the roadmap itself, namely of a real algebraic curve, can be analyzed in time cubic in its size.
Finally, we illustrate the practical applicability of these methods through original implementations leveraging recent advances in polynomial system solving software.