Abstract
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(n4) 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(k2n4) 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.
Original language | English |
---|---|
Journal | Algorithmica |
Volume | 13 |
Issue number | 6 |
Pages (from-to) | 539-552 |
Number of pages | 14 |
ISSN | 0178-4617 |
DOIs | |
Publication status | Published - 01.06.1995 |