A baby steps/giant steps Monte Carlo algorithm for computing roadmaps in smooth compact real hypersurfaces

2009/02/10 by Mohab Safey El Din, Din, Mohab Safey El, Éric Schost +1
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Polynomial and algebraic computation #Symbolic Computation (cs.SC)

paper · pdf · doi:10.48550/arxiv.0902.1612

openalex publication_date 2009/02/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of constructing roadmaps of real algebraic sets. The 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 sⁿlog(s) D^O(n2) operations in ℚ; a deterministic version runs in time sⁿ log(s) D^O(n4). The next improvement was due to Basu, Pollack and Roy, with an algorithm of deterministic cost s^d+1 D^O(n2) for the more general problem of computing roadmaps of semi-algebraic sets (d ≤ n is the dimension of an associated object). We give a Monte Carlo algorithm of complexity (nD)^O(n^1.5) for the problem of computing a roadmap of a compact hypersurface V of degree D in n variables; we also have to assume that V has a finite number of singular points. Even under these extra assumptions, no previous algorithm featured a cost better than D^O(n2).

Related

• Computing roadmaps in unbounded smooth real algebraic sets II: algorithm and complexity
• A nearly optimal algorithm for deciding connectivity queries in smooth\n and bounded real algebraic sets
• A baby step-giant step roadmap algorithm for general algebraic sets
• Computing roadmaps in unbounded smooth real algebraic sets I: connectivity results
• Sampling-based Roadmap Planners are Probably Near-Optimal after Finite Computation