DISASSEMBLING TWO-DIMENSIONAL COMPOSITE PARTS VIA TRANSLATIONS

Publisher Website
Google Scholar
Abstract
This paper deals with the computational complexity of disassembling 2-dimensional composite parts (comprised of M simple n-vertex polygons) via collision-free translations. The first result of this paper is an O(Mn+M log M) algorithm for computing a sequence of translations (performed in a common direction) to disassemble composite parts. The algorithm improves on the O(Mn log Mn) bound previously established for this problem and is easily seen to be optimal. The problem had been posed by Nurmi and by Toussaint. The second result of this paper is an Ω(Mn+M log M) lower bound proof for the problem of detecting whether a composite part can be disassembled, or contains interlocking subparts. Thus, detecting the existence of a disassembly sequence is as hard as computing one. As a consequence, the algorithm for computing a disassembly sequence is optimal also for the detecting problem.

This publication has 0 references indexed in Scilit: