Connectivity in real algebraic sets : algorithms and applications
Connexité dans les ensembles algébriques réels : algorithmes et applications
Résumé
This PhD thesis focuses on the design and the analysis of computer algebra algorithms for solving polynomial systems. More precisely, we address the problems of counting the number of connected components of sets of real solutions to systems of polynomial equations with real coefficients and of answering connectivity queries over such real solution sets. These problems are central in real algebraic geometry and find applications in robotics. The chosen framework is the one of roadmaps, introduced by Canny in 1988: it consists in computing a curve, included in the solution set under consideration, which has a connected intersection with all its connected components. We design an algorithm which, under some regularity assumptions which are satisfied generically, computes such roadmaps in time subquadratic w.r.t. the output size. This latter quantity is nearly optimal. This extends to non compact situations the best complexity results known for such a computational problem. We also show that the cost to compute the number of connected components of a real algebraic curve (lying in a space of arbitrary dimension) is nearly the same as the one of computing the topology of its projection on a generic plane. Last, by combining these results with algorithms of real algebraic geometry, we design an algorithm to decide the cuspidality of robots.
Cette thèse de doctorat porte sur la conception et l'analyse d'algorithmes, relevant du calcul formel, pour la résolution de systèmes polynomiaux. Plus précisément, nous considérons le problème du comptage du nombre de composantes connexes de l'ensemble des solutions réelles de systèmes d'équations polynomiales à variables réelles, ainsi que le problème de décider si deux solutions réelles d'un tel système vivent dans une même composante connexe de son ensemble de solutions réelles. Ces problèmes sont centraux en géométrie algébrique réelle et trouvent des applications en robotique. Le cadre méthodologique choisi est celui du calcul de cartes routières, introduit par Canny en 1988 : il s'agit de calculer une courbe contenue dans l'ensemble des solutions dont l'intersection avec chacune de ses composantes connexes est connexe. Nous décrivons un algorithme calculant de telles cartes routières qui, sous des hypothèses de régularité satisfaites génériquement, a une complexité sous-quadratique en la taille de la sortie, cette dernière étant asymptotiquement quasi optimale. Ceci étend aux cas non compacts les meilleures complexités connues pour ce problème. Nous montrons aussi que le coût du calcul de nombre de composantes connexes d'une courbe algébrique réelle (vivant dans un espace de dimension arbitraire) est similaire au coût du calcul de la topologie de sa projection sur un plan générique. Enfin, nous montrons comment ces avancées, combinées aux algorithmes de la géométrie algébrique réelle permettent de concevoir un algorithme testant la cuspidalité de mécanismes articulés.
| Origine | Version validée par le jury (STAR) |
|---|