On the complexity of a single cell in certain arrangements of surfaces related to motion planning (Q1314439)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the complexity of a single cell in certain arrangements of surfaces related to motion planning |
scientific article |
Statements
On the complexity of a single cell in certain arrangements of surfaces related to motion planning (English)
0 references
28 July 1994
0 references
This interesting paper contains results for motion-planning problems with three degrees of freedom where the entire free configuration space could be in cubic size. The author obtains almost tight near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in arrangements of \(n\) surfaces in 3-space which are interesting for motion planning problems. He gives also topological and combinatorial conditions for such near-quadratic upper bounds. He studies applications for three- link arm arrangements and for special arrangements of triangles in space. Among others the following theorem about algorithms is proved: A single cell in an arrangement of surfaces induced by the motion planning for a telescope arm among \(n\) point obstacles in the plane can be computed in \(O(n^ 2\log^ 2n)\) time and \(O(n^ 2\log n)\) space. Interesting open problems are discussed.
0 references
motion-planning problems
0 references
combinatorial complexity
0 references
arrangements
0 references