Forschungsleitung (Direction de recherche) : Mohab SAFEY EL DIN

Connectivity in real algebraic sets: algorithms and applications

This Ph.D. 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 a 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 of computing the number of connected components of a real algebraic curve (lying in a space of arbitrary dimensions) is nearly the same as that of computing the topology of its projection on a generic plane. Lastly, by combining these results with algorithms of real algebraic geometry, we design an algorithm to decide the cuspidality of robots.

Publikationen 2022-2024

• 2024
  • R. Prébet, M. Safey El Din, E. Schost : “Computing roadmaps in unbounded smooth real algebraic sets II: algorithm and complexity”, (2024)
  • R. Prébet, M. Safey El Din, E. Schost : “Computing roadmaps in unbounded smooth real algebraic sets I: connectivity results”, Journal of Symbolic Computation, vol. 120, pp. 102234, (Elsevier) (2024)
• 2023
  • R. Prébet : “Connectivity in real algebraic sets: algorithms and applications”, these, verteidigung einer doktorarbeit 20.12.2023, forschungsleitung (direction de recherche) Safey el din, Mohab (2023)
  • N. Islam, A. Poteaux, R. Prébet : “Algorithm for connectivity queries on real algebraic curves”, ISSAC '23: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation, Tromsø, Norway (2023)
• 2022
  • D. Chablat, R. Prébet, M. Safey El Din, D. Salunkhe, Ph. Wenger : “Deciding Cuspidality of Manipulators through Computer Algebra and Algorithms in Real Algebraic Geometry”, ISSAC '22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, Lille, France (2022)