TR-134: Separating a Polyhedron by One Translation from a Set of Obstacles

Abstract

We present efficient algorithms for several problems of movable. separability in 3-dimensional apace. The first algorithm determines all directions in which a convex polyhedron can be translated through a planar convex polygon. The algorithm runs in O(n) time. This is a considerable improvement over the previous O(n2 log n) time algorithm of [17]. 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 plane-sweep 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 O(n2 ) time computation of the Minkowski differences of the polyhedra.