Assembly sequences for polyhedra

The problem of finding sequences of motions for the assembly of a given object consisting of polyhedral parts arises in assembly planning. We describe an algorithm to compute the set of all translations separating two polyhedra with n vertices in O(n⁴) steps and show that this is optimal. Given an assembly of k polyhedra with a total of n vertices, an extension of this algorithm identifies a valid translation and removable subassembly in O(k²n⁴) steps if one exists. Based on the second algorithm, a polynomial-time method for finding a complete assembly sequence consisting of single translations is derived. An implementation incorporates several changes to achieve better average-case performance; experimental results obtained for simple assemblies are described.