Assembly sequences for polyhedra

A. Schweikard*, R. H. Wilson

*Corresponding author for this work
7 Citations (Scopus)

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 languageEnglish
JournalAlgorithmica
Volume13
Issue number6
Pages (from-to)539-552
Number of pages14
ISSN0178-4617
DOIs
Publication statusPublished - 01.06.1995

Fingerprint

Dive into the research topics of 'Assembly sequences for polyhedra'. Together they form a unique fingerprint.

Cite this