### 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.