BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-91-1387
       ENTRY:: September 02, 1994
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Assembling polyhedra with single translations
        TYPE:: Technical Report
      AUTHOR:: Wilson, Randall
      AUTHOR:: Schweikard, Achim
        DATE:: October 1991
       PAGES:: 18
    ABSTRACT:: The problem of partitioning an assembly of polyhedral objects
               into two subassemblies that can be separated 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(k2 n4) 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 composite objects
               consisting of isothetic polyhedra are described.
       NOTES:: [Adminitrivia V1/RAM/19940902]
         END:: STAN//CS-TR-91-1387