Computing roadmaps in unbounded smooth real algebraic sets I: Connectivity results

Answering connectivity queries in real algebraic sets is a fundamental problem in effective real algebraic geometry that finds many applications in e.g. robotics where motion planning issues are topical. This computational problem is tackled through the computation of so-called roadmaps which are real algebraic subsets of the set V under study, of dimension at most one, and which have a connected intersection with all semi-algebraically connected components of V. Algorithms for computing roadmaps rely on statements establishing connectivity properties of some well-chosen subsets of V, assuming that V is bounded. In this paper, we extend such connectivity statements by dropping the boundedness assumption on V. This exploits properties of so-called generalized polar varieties, which are critical loci of V for some well-chosen polynomial maps.& COPY; 2023 Elsevier Ltd. All rights reserved.

Automated summary

This paper presents a fundamental problem in effective real algebraic geometry, which is answering connectivity queries in real algebraic sets. This problem has many applications in robotics, particularly in motion planning. The problem is solved by computing roadmaps, which are real algebraic subsets of the set under study, with dimension at most one and a connected intersection with all semi-algebraically connected components. The algorithms for computing roadmaps rely on connectivity properties of selected subsets, assuming boundedness of the set. The paper extends these connectivity statements by removing the boundedness assumption and utilizing generalized polar varieties.