- Computer Science Laboratory

PRÉBET Rémi

PhD Student at Sorbonne University
Team : PolSys
https://rprebet.github.io/
https://rprebet.github.io/

Supervision : 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.


Phd defence : 12/20/2023

Jury members :

Laurent Busé, Directeur de recherche, INRIA Sophia, France [Rapporteur]
Alicia Dickenstein, Professeure, Universidad de Buenos Aires [Rapporteur]
Peter Bürgisser, Professeur, Technical University of Berlin
Fatemeh Mohammadi, Professeure, KU Leuven
Jean Ponce, Professeur des Universités, École Normale Supérieure-PSL & New York University
Bernd Sturmfels, Professeur, University of California à Berkeley & Directeur du MPI Leipzig
Émmanuel Trélat, Professeur des Universités, Sorbonne Université
Éric Schost, Professeur, University of Waterloo (Invité)
Mohab Safey El Din, Professeur des Universités, Sorbonne Université

Departure date : 12/31/2023

2022-2024 Publications