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

Pubblicazioni 2022-2024