On the complexity of a single cell in certain arrangements of surfaces related to motion planning (Q1314439)

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.