Assembling polyhedra with single translations

Randall H. Wilson; Achim Schweikard

Assembling polyhedra with single translations

Institute of Robotics and Cognitive Systems

Stanford University

Abstract

The problem of partitioning an assembly of polyhedral objects into two subassemblies that can be separated arises in assembly planning. The authors 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 performances. Experimental results obtained for composite objects consisting of isothetic polyhedra are described.

Original language	English
Pages	2392-2397
Number of pages	6
Publication status	Published - 01.12.1992
Event	Proceedings of the 1992 IEEE International Conference on Robotics and Automation - Nice, France Duration: 12.05.1992 → 14.05.1992 Conference number: 17601

Conference

Conference	Proceedings of the 1992 IEEE International Conference on Robotics and Automation
Country/Territory	France
City	Nice
Period	12.05.92 → 14.05.92

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

https://dl.acm.org/citation.cfm?id=892515

Cite this

@conference{8fce12d9b9864affa95213265a6d2e57,

title = "Assembling polyhedra with single translations",

abstract = "The problem of partitioning an assembly of polyhedral objects into two subassemblies that can be separated arises in assembly planning. The authors 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 performances. Experimental results obtained for composite objects consisting of isothetic polyhedra are described.",

author = "Wilson, {Randall H.} and Achim Schweikard",

year = "1992",

month = dec,

day = "1",

language = "English",

pages = "2392--2397",

note = "Proceedings of the 1992 IEEE International Conference on Robotics and Automation <br/> ; Conference date: 12-05-1992 Through 14-05-1992",

}

TY - CONF

T1 - Assembling polyhedra with single translations

AU - Wilson, Randall H.

AU - Schweikard, Achim

N1 - Conference code: 17601

PY - 1992/12/1

Y1 - 1992/12/1

N2 - The problem of partitioning an assembly of polyhedral objects into two subassemblies that can be separated arises in assembly planning. The authors 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 performances. Experimental results obtained for composite objects consisting of isothetic polyhedra are described.

AB - The problem of partitioning an assembly of polyhedral objects into two subassemblies that can be separated arises in assembly planning. The authors 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 performances. Experimental results obtained for composite objects consisting of isothetic polyhedra are described.

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-0026998764&origin=inward&txGid=0ad29a654330a18195abe4f8fc0dae82

M3 - Conference Papers

SP - 2392

EP - 2397

T2 - Proceedings of the 1992 IEEE International Conference on Robotics and Automation <br/>

Y2 - 12 May 1992 through 14 May 1992

ER -

Assembling polyhedra with single translations

Abstract

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this