A Baby Steps/Giant Steps Probabilistic Algorithm for Computing Roadmaps in Smooth Bounded Real Hypersurface

摘要

We consider the problem of constructing roadmaps of real algebraic sets. This problem was introduced by Canny to answer connectivity questions and solve motion planning problems. Given s polynomial equations with rational coefficients, of degree D in n variables, Canny's algorithm has a Monte Carlo cost of sn log(s)D~o(n~2 operations in ?; a deterministic version runs in time sn log(s)D~o(n~2. A subsequent improvement was due to Basu, Pollack, and Roy, with an algorithm of deterministic cost s~(d+1)D~0(n~2 for the more general problem of computing roadmaps of a semi-algebraic set (d≤n is the dimension of an associated object). We give a probabilistic algorithm of complexity (nD)~0(n~(1.5) for the problem of computing a roadmap of a closed and bounded hypersurface V of degree D in n variables, with a finite number of singular points. Even under these extra assumptions, no previous algorithm featured a cost better than D~0(n~2.