ON TRANSLATIONAL MOTION PLANNING OF A CONVEX POLYHEDRON IN 3-SPACE

Let B be a convex polyhedron translating in 3-space amidst k convex po lyhedral obstacles A(1),...,A(k) with pairwise disjoint interiors. The free configuration space (space of all collision-free placements) of B can be represented as the complement of the union of the Minkowski s ums P-i = A(i) + (-B), for i = 1,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log k), and t hat it can be Omega(nk alpha(k)) in the worst case, where n is the tot al complexity of the individual Minkowski sums P-1,...,P-k. We also de rive an efficient randomized algorithm that constructs this configurat ion space in expected time O(nk log k log n).