Construction of roadmaps in semi-algebraic sets (Q1311619): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:53, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Construction of roadmaps in semi-algebraic sets |
scientific article |
Statements
Construction of roadmaps in semi-algebraic sets (English)
0 references
5 March 1995
0 references
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)}\).
0 references
construction of a roadmap
0 references
compact semialgebraic set
0 references