Abstract:

Abstract: Consider the following questions (coming for instance from motion planning problems): given two points on a real algebraic set $S$, do they belong to the same connected component? If so, how can we connect them?

Canny introduced "roadmaps" as a way to reduce such problems to computations with curves only. Given $s$ polynomial equations with rational coefficients, of degree $d$ in $n$ variables, Canny's algorithm, and its generalizations by Basu, Pollack and Roy, have a cost polynomial in $(s D^n)^n$.

This is depressingly high; as a result, none of these algorithms is practical for realistic instances. Indeed, one would rather expect a cost polynomial in $s D^n$. I will present ongoing work with Mohab Safey El Din toward this goal.