.png){kind=icon}
.png){kind=icon}
Return
Computing roadmaps in unbounded smooth real algebraic sets II: Algorithm and complexity
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jsc.2025.102532.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A roadmap for an algebraic set V defined by polynomials with coefficients in the field Q of rational numbers is an algebraic curve contained in V whose intersection with all connected components of V boolean AND Rn is connected. These objects, introduced by Canny, can be used to answer connectivity queries over V boolean AND Rn provided that they are required to contain the finite set of query points P subset of V ; in this case, we say that the roadmap is associated to (V,P). In this paper, we make effective a connectivity result we previously proved, to design a Monte Carlo algorithm which, on input (i) a finite sequence of polynomials defining V (and satisfying some regularity assumptions) and (ii) an algebraic representation of finitely many query points P in V, computes a roadmap for (V, P). This algorithm generalizes the nearly optimal one introduced by the last two authors by dropping a boundedness assumption on the real trace of V. The output size and running times of our algorithm are both polynomial in (nD)n log d, where D is the maximal degree of the input equations and d is the dimension of V. As far as we know, the best previously known algorithm dealing with such sets has an output size and running time respectively polynomial in (nlognD)n log nand (nlognD)nlog2n. (c) 2025 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Keywords:
Computational real algebraic geometry
Real algebraic sets
Critical points
Roadmaps
Algorithm
Complexity
Journal
J
IF:
1.1
Papers:
37
Citations:
0
View more organizations