Technical Report No. 11, April 1988 - Abstract

Otto Nurmi, Jörg-Rüdiger Sack:
Separating a Polyhedron by One Translateion from a Set of Obstacles

This report is not available in electronic form!

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 polygon. The algorithm runs in O(n) time. This is a considerable improvement over the previous O(n^2*log n) time algorithm of Toussaint. 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(n^2) time computation of the Minkowski differences of the polyhedra.