Computing roadmaps of general semi-algebraic sets
[For the entire collection see Zbl 0758.00016.] The roadmaps were invented by the author [``The complexity of robot motion planning. (Thesis; Cambridge 1988)] for the purpose of finding paths in semi-algebraic sets. The original construction proposed by the author worked under the hypothesis that the semi-algebraic set was compact, and defined by polynomials in ``general position. The present paper explains how to retreat from the general case to this hypothesis, introducing several infinitesimals for perturbations. The original roadmap algorithm is called for this perturbated set; it is not precisely stated what information this gives about the nonperturbated set. The complexity of the (deterministic) algorithm, in terms of the dimension of ambient space \(n\), the number of polynomials \(k\) and the maximum degree \(d\), is \((k^ n\log^ 2k)d^{O(n^ 4)}\). The author insists on the fact that the combinatorial complexity (dependance upon \(k)\) is nearly optimal.
- Computing Roadmaps of General Semi-Algebraic Sets
- scientific article; zbMATH DE number 1256732
- Computing roadmaps of semi-algebraic sets on a variety
- Computing roadmaps of semi-algebraic sets on a variety. (Extended abstract)
- Construction of roadmaps in semi-algebraic sets
- Constructing roadmaps of semi-algebraic sets. I: Completeness
- Computing roadmaps in smooth real algebraic sets
- A baby step-giant step roadmap algorithm for general algebraic sets
- Computing with semi-algebraic sets: relaxation techniques and effective boundaries
- scientific article; zbMATH DE number 1254270
- An algorithmic approach to some problems in terrain navigation
- Constructing roadmaps of semi-algebraic sets. I: Completeness
- Determinantal formulae for the solution set of zero-dimensional ideals
- Construction of roadmaps in semi-algebraic sets
- A convex geometric approach to counting the roots of a polynomial system
- Computing with semi-algebraic sets: relaxation techniques and effective boundaries
- Computing Roadmaps of General Semi-Algebraic Sets
- Computing roadmaps in smooth real algebraic sets
- Unstructured path problems and the making of semirings
- scientific article; zbMATH DE number 1256732 (Why is no real title available?)
- Computing roadmaps of semi-algebraic sets on a variety. (Extended abstract)
- Divide and conquer roadmap for algebraic sets
- Computing roadmaps of semi-algebraic sets on a variety
- A baby step-giant step roadmap algorithm for general algebraic sets
- Computing roadmaps in unbounded smooth real algebraic sets. I: Connectivity results
- An opportunistic global path planner
- Robot navigation functions on manifolds with boundary
This page was built for publication: Computing roadmaps of general semi-algebraic sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4038743)
