On the complexity of a single cell in certain arrangements of surfaces related to motion planning |
| |
Authors: | Dan Halperin |
| |
Institution: | (1) Department of Computer Science, Tel-Aviv University, 69978 Tel-Aviv, Israel;(2) Present address: Robotics Laboratory, Department of Computer Science, Stanford University, 94305 Stanford, CA, USA |
| |
Abstract: | We obtain near-quadratic upper bounds on the maximum combinatorial complexity of a single cell in certain arrangements ofn surfaces in 3-space where the lower bound for this quantity is Ω(n
2) or slightly larger. We prove a theorem that identifies a collection of topological and combinatorial conditions for a set
of surface patches in space, which make the complexity of a single cell in an arrangement induced by these surface patches
near-quadratic. We apply this result to arrangements related to motion-planning problems of two types of robot systems with
three degrees of freedom and also to a special type of arrangements of triangles in space. The complexity of the entire arrangement
in each case that we study can be Θ(n
3) in the worst case, and our single-cell bounds are of the formO(n
2
α(n)), O(n
2
logn), orO(n
2
α(n)logn). The only previously known similar bounds are for the considerably simpler arrangements of planes or of spheres in space,
where the bounds are Θ(n) and Θ(n
2), respectively. For some of the arrangements that we study we derive near-quadratic-time algorithms to compute a single cell.
A preliminary version of this paper has appeared inProc. 7th ACM Symposium on Computational Geometry, North Conway, NH, 1991, pp. 314–323. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|