Separating a polyhedron by one translation from a set of obstacles
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 , 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.