Assembly sequences for polyhedra

Type of publication:  Artikel
Zeitschrift: Algorithmica
Band: 13
Nummer: 6
Jahr: 1995
Monat: Juni
Seiten: 539--552
ISSN: 1432-0541
DOI: 10.1007/BF01189068
Abriss: 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 withn vertices inO(n4) steps and show that this is optimal. Given an assembly ofk polyhedra with a total ofn 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.
Nutzerfelder: owner={Lars}, timestamp={2007.02.16},
Schlagworte: Arrangement computation in the plane, Assembly planning, Separating polyhedra
Autoren: Schweikard, Achim
Wilson, R. H.