On translational motion planning in 3-space

Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A₁,....,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 sums P_i A_i ⊕ (-B), for i = l,...,k. We show that the combinatorial complexity of the free configuration space of B is O(nk log² k), where n is the total complexity of the individual Minkowski sums P₁,..., P_k. The bound is almost tight in the worst case. We also derive an efficient randomized algorithm that constructs this configuration space in expected time O(nk log³ k).