A baby steps/giant steps Monte Carlo algorithm for computing roadmaps in smooth compact real hypersurfaces

1 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : We consider the problem of constructing roadmaps of real algebraic sets. The problem was introduced by Canny to answer connectivity questions and solve motion planning problems. Given $s$ polynomial equations with rational coefficients, of degree $D$ in $n$ variables, Canny's algorithm has a Monte Carlo cost of $s^n\log(s) D^{O(n^2)}$ operations in $\mathbb{Q}$; a deterministic version runs in time $s^n \log(s) D^{O(n^4)}$. The next improvement was due to Basu, Pollack and Roy, with an algorithm of deterministic cost $s^{d+1} D^{O(n^2)}$ for the more general problem of computing roadmaps of semi-algebraic sets ($d \le n$ is the dimension of an associated object). We give a Monte Carlo algorithm of complexity $(nD)^{O(n^{1.5})}$ for the problem of computing a roadmap of a compact hypersurface $V$ of degree $D$ in $n$ variables; we also have to assume that $V$ has a finite number of singular points. Even under these extra assumptions, no previous algorithm featured a cost better than $D^{O(n^2)}$.
Keywords :
Type de document :
Article dans une revue
Journal of Discrete and Computational Geometry, Springer, 2011, 45 (1), pp.181-220. 〈10.1007/s00454-009-9239-2〉
Domaine :

Littérature citée [30 références]

https://hal.inria.fr/inria-00359748
Contributeur : Mohab Safey El Din <>
Soumis le : lundi 9 février 2009 - 12:07:42
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : mardi 8 juin 2010 - 22:05:35

Fichiers

RR-6832.pdf
Fichiers produits par l'(les) auteur(s)

Citation

Mohab Safey El Din, Éric Schost. A baby steps/giant steps Monte Carlo algorithm for computing roadmaps in smooth compact real hypersurfaces. Journal of Discrete and Computational Geometry, Springer, 2011, 45 (1), pp.181-220. 〈10.1007/s00454-009-9239-2〉. 〈inria-00359748〉

Métriques

Consultations de la notice

318

Téléchargements de fichiers