Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results (Q6170822)

This article could be considered as a continuation of a series of articles that aim to devise efficient algorithms for the calculation of roadmaps for algebraic sets. Roughly speaking, given an algebraic set \(V \subset \mathbb{C}^n\) defined over \(\mathbb{Q}\), a roadmap of \(V\) is a real algebraic subset of \(V \cap\mathbb{R}^n\), defined over \(\mathbb{Q}\), of dimension at most one that have a connected intersection with all connected components of \(V\). These algebraic objects are used to answer connectivity queries in effective real algebraic geometry, with applications, for instance, to motion planning. Algorithms for computing roadmaps rely on statements establishing connectivity properties of some well-chosen subsets of \(V\), assuming that \(V\) is bounded. Thus, in [\textit{M. Safey el Din} and \textit{ Schost}, Discrete Comput. Geom. 45, No. 1, 181--220 (2011; Zbl 1213.14110)], authors introduced a theorem that establishes connectivity and existing statements which allow to define a roadmap, assuming that \(V \cap\mathbb{R}^n\) is bounded. Besides, such an article also introduced a probabilistic algorithm of complexity \((nD)^{O(n\sqrt{n})}\), where \(D\) is the maximum degree of input equations defining \(V\). In [\textit{M. Safey El Din} and \textit{ Schost}, J. ACM 63, No. 6, Article No. 48, 37 p. (2017; Zbl 1426.68311)], they improved the algorithm using \((nD)^{6n\log_2(d)}\) arithmetic operations in \(\mathbb{Q}\), assuming that \(V\) is \(d\)-equidimensional and also that \(V \cap\mathbb{R}^n\) is bounded. In this paper the boundedness condition is removed. Hence, the main goal is to prove a new connectivity statement (Theorem 1.1) with no boundedness assumption and the same freedom brought by the one of [\textit{M. Safey el Din} and \textit{ Schost}, Discrete Comput. Geom. 45, No. 1, 181--220 (2011; Zbl 1213.14110)]. In more concrete terms, Theorem 1.1 asserts that, under some assumptions, the union of generalized polar varieties (Definition 2.4) and fibers have a non-empty and semi-algebraically connected intersection with each semi-algebraically connected component of \(V \cap\mathbb{R}^n\). This statement will be used to design new roadmap algorithms in upcoming work.