We present efficient algorithms for several problems of movable separability in 3-dimensional space. The first algorithm determines all directions in which a convex polyhedron can be translated through a planar convex polygonal window. The algorithm runs in linear time. This is a considerable improvement over the previous O(n2logn) time algorithm of [17], where n is the total number of vertices in the objects. The second algorithm computes, in O(n) time, all directions in which a convex polyhedron can be translated to infinity without collisions with a convex obstacle (n is the number of vertices of the polyhedra). A generalization of the planesweep technique, called “sphere-sweep”, is given and provides an efficient algorithm for the last problem which is: determine all directions in which a convex polyhedron can be separated from a set of convex obstacles. Our results are obtained by avoiding the standard technique of motion planning problems, the Ω(n2) time computation of the Minkowski differences of the polyhedra.

Additional Metadata
Persistent URL dx.doi.org/10.1007/3-540-50728-0_44
Series Lecture Notes in Computer Science
Citation
Nurmi, O. (Otto), & Sack, J.-R. (1989). Separating a polyhedron by one translation from a set of obstacles. In Lecture Notes in Computer Science. doi:10.1007/3-540-50728-0_44