Computing roadmaps in unbounded smooth real algebraic sets II: algorithm and complexity
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917090562146304 |
|---|---|
| author | Prébet, Rémi Din, Mohab Safey El Schost, Éric |
| author_facet | Prébet, Rémi Din, Mohab Safey El Schost, Éric |
| contents | A roadmap for an algebraic set $V$ defined by polynomials with coefficients in the field $\mathbb{Q}$ of rational numbers is an algebraic curve contained in $V$ whose intersection with all connected components of $V\cap\mathbb{R}^{n}$ is connected. These objects, introduced by Canny, can be used to answer connectivity queries over $V\cap \mathbb{R}^{n}$ provided that they are required to contain the finite set of query points $\mathcal{P}\subset V$; in this case, we say that the roadmap is associated to $(V, \mathcal{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 $\mathcal{P}$ in $V$, computes a roadmap for $(V, \mathcal{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 $(n^{\log{n}}D)^{n\log n}$ and $(n^{\log{n}}D)^{n\log^2 n}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_03111 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Computing roadmaps in unbounded smooth real algebraic sets II: algorithm and complexity Prébet, Rémi Din, Mohab Safey El Schost, Éric Symbolic Computation Algebraic Geometry A roadmap for an algebraic set $V$ defined by polynomials with coefficients in the field $\mathbb{Q}$ of rational numbers is an algebraic curve contained in $V$ whose intersection with all connected components of $V\cap\mathbb{R}^{n}$ is connected. These objects, introduced by Canny, can be used to answer connectivity queries over $V\cap \mathbb{R}^{n}$ provided that they are required to contain the finite set of query points $\mathcal{P}\subset V$; in this case, we say that the roadmap is associated to $(V, \mathcal{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 $\mathcal{P}$ in $V$, computes a roadmap for $(V, \mathcal{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 $(n^{\log{n}}D)^{n\log n}$ and $(n^{\log{n}}D)^{n\log^2 n}$. |
| title | Computing roadmaps in unbounded smooth real algebraic sets II: algorithm and complexity |
| topic | Symbolic Computation Algebraic Geometry |
| url | https://arxiv.org/abs/2402.03111 |