FoCM 2014 conference
Workshop A6 - Real Number Complexity
December 13, 17:00 ~ 17:30 - Room A22
On the computation of roadmaps of real algebraic sets
Eric Schost
Western University, Canada - eschost@uwo.ca
We consider the question of constructing roadmaps of real algebraic sets, which was introduced by Canny to answer connectivity questions and solve motion planning problems. Canny’s algorithm is recursive, but decreases the dimension only by one through each recursive call.
In this talk, we present a divide-and-conquer version of Canny’s algorithm, where the dimension is halved through each recursive call. The input is a compact complete intersection $V$ given by polynomials of degree $D$ in $n$ variables; we also have to assume that $V$ has a finite number of singular points.
We also mention results of a preliminary implementation, and may indicate how the calculation of points on some Thom-Boardman strata could explain some of these results.
Joint work with Mohab Safey El Din (Universite Pierre et Marie Curie (Paris 6), France).