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

DOI10.1016/J.JSC.2023.102234MaRDI QIDQ6170822zbMATH OpenFDO

Publication date 10 August 2023

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2203.03961

computational real algebraic geometry critical points real algebraic sets roadmaps

Real algebraic sets (14P05) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Computational real algebraic geometry (14Q30) Symbolic computation and algebraic computation (68W30)

Abstract: 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.

Review text

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.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6170822)