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

From MaRDI portal
scientific article; zbMATH DE number 7725359
Language Label Description Also known as
English
Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results
scientific article; zbMATH DE number 7725359

    Statements

    Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results (English)
    0 references
    0 references
    0 references
    0 references
    10 August 2023
    0 references
    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.
    0 references
    critical points
    0 references
    roadmaps
    0 references
    real algebraic sets
    0 references
    computational real algebraic geometry
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references