A baby step-giant step roadmap algorithm for general algebraic sets (Q486687)

The article is concerned with the computation of a roadmap for a semialgebraic set \(S\subset R^k\), where \(R\) is real closed field (for example, the field of real numbers). A roadmap for \(S\) is a semialgebraic curve in \(S\) having nonempty connected intersection with each connected component of \(S\). The notion of a roadmap was introduced by Canny in order to design algorithms for deciding whether two points belong to the same semialgebraically connected component of a semialgebraic set (see [\textit{J. Canny}, The complexity of robot motion planning. Cambridge (PhD thesis) (1988)]). In several papers, the construction of a roadmap of a given semialgebraic set \(S\) is reduced to one for certain \((k-1)\)--dimensional slices of \(S\), which are obtained fixing the first coordinate. The construction of a roadmap associated to the real algebraic variety defined by a polynomial \(Q\in R[X_1,\ldots,X_k]\) of degree at most \(d\) following these ideas requires \(d^{\mathcal{O}(k^2)}\) arithmetic operations. In [\textit{M. Safey el Din} and \textit{É. Schost}, Discrete Comput. Geom. 45, No. 1, 181--220 (2011; Zbl 1213.14110)], a new recursive baby step-giant step scheme was designed for smooth bounded real algebraic hypersurfaces. The scheme requires \(d^{\mathcal{O}(k\sqrt{k})}\) arithmetic operations, and relies on the choice of generic coordinates to ensure smoothness of certain polar varieties, that is, the degeneracy loci of linear projections, of the input hypersurface. On the other hand, an algorithm in [\textit{S. Basu} et al., Algorithms in real algebraic geometry. 2nd ed. Berlin: Springer (2006; Zbl 1102.14041)] relies on an infinitesimal deformation of the input real algebraic set so that the original coordinates are good. In the paper under review, techniques of these two works are combined in order to obtain a deterministic symbolic algorithm computing a roadmap of a given (eventually nonsmooth) real algebraic set \(Z\subset R^k\). If \(Z\) is defined by polynomials of degree at most \(d\geq 2\), then the algorithm performs \(d^{\mathcal{O}(k\sqrt{k})}\) arithmetic operations. As a consequence, it is shown that both counting the number of connected components of \(Z\), and deciding whether two points of \(Z\) belong to the same connected component of \(Z\), can be determined with \(d^{\mathcal{O}(k\sqrt{k})}\) arithmetic operations. For this purpose, the authors rely on the computation of a finite set of points intersecting every connected component of the the given real algebraic set \(Z\). For \(Z\) smooth, the set of critical points of the projection to the \(X_1\)-coordinate on \(Z\) is computed. On the other hand, in the nonsmooth case \(X_1\) pseudocritical points are considered, namely limits of the critical points of the projection to the \(X_1\)-coordinate of an infinitesimal deformation of \(Z\). Throughout the computations, points and curve segments are represented by suitable Thom encodings. The paper ends with a technical appendix, where the computation of limits of bounded points and curve segments is considered in detail.