On translational motion planning in 3-space
Boris S. Aronov, Micha Sharir · 1994
Let B be a convex polyhedron translating in 3-space amidst k convex polyhedral obstacles A1,…,Ak 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 Pi=Ai⊕(-B), for i=1,…,k. We show that the combinatorial complexity of the free configuration space of B is O(nklog2k), where n is the total complexity of the individual Minkowski sums P1,…,Pk. 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(nklog3k).