A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets

Mohab Safey El Din 1 Éric Schost 2
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : A roadmap for a semi-algebraic set $S$ is a curve which has a non-empty and connected intersection with all connected components of $S$. Hence, this kind of object, introduced by Canny, can be used to answer connectivity queries (with applications, for instance, to motion planning) but has also become of central importance in effective real algebraic geometry, since it is used in higher-level algorithms. In this paper, we provide a probabilistic algorithm which computes roadmaps for smooth and bounded real algebraic sets. Its output size and running time are polynomial in $(nD)^{n\log(d)}$, where $D$ is the maximum of the degrees of the input polynomials, $d$ is the dimension of the set under consideration and $n$ is the number of variables. More precisely, the running time of the algorithm is essentially subquadratic in the output size. Even under our assumptions, it is the first roadmap algorithm with output size and running time polynomial in $(nD)^{n\log(d)}$.
Type de document :
Article dans une revue
Journal of the ACM (JACM), Association for Computing Machinery, 2017, 63 (6), pp.48:1--48:37. 〈10.1145/2996450〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00849057
Contributeur : Mohab Safey El Din <>
Soumis le : jeudi 27 octobre 2016 - 12:02:52
Dernière modification le : vendredi 31 août 2018 - 09:25:58
Document(s) archivé(s) le : vendredi 3 février 2017 - 12:35:56

Fichiers

roadmaps-JACM-new-hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Mohab Safey El Din, Éric Schost. A nearly optimal algorithm for deciding connectivity queries in smooth and bounded real algebraic sets. Journal of the ACM (JACM), Association for Computing Machinery, 2017, 63 (6), pp.48:1--48:37. 〈10.1145/2996450〉. 〈hal-00849057v3〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

121