Construction of roadmaps in semi-algebraic sets (Q1311619)

The authors describe an algorithm for constructing a roadmap for a compact semialgebraic set \(S \subset R^ n\). This is similar to J. Canny's algorithm, but somewhat simpler and is more general. If the number of defining equations of \(S\) is \(k\) and \(n\) is the number of variables, and \(d\) is the maximal degree, then the algorithm runs in time \((kd)^{O(n^ 3)}\).