Group Seminar: SC: Roadmap algorithms in real algebraic geometry for deciding connectivity queries

Speaker: Mohab Safey El Din (Sorbonne, Paris), Location: SP2 416-2

SC: Roadmap algorithms in real algebraic geometry for deciding connectivity queries

Speaker: Mohab Safey El Din (Sorbonne, Paris)
Date: June 6, 2017 14:00
Location: SP2 416-2

Roadmaps have been introduced by Canny as a tool for deciding connectivity queries in semi-algebraic sets: these are curves which have a non-empty and connected intersection with the semi-algebraic set under consideration. This talk will review recent progress in the computation of roadmaps in the case of algebraic sets. These have led to nearly optimal algorithms; we will focus on those dealing with real algebraic sets under some regularity assumptions. These algorithms are subquadratic in the output size which is essentially (n^2D)^(n\log(n)) where n is the dimension of the ambient space and D the maximum degree of the input polynomials.