On the complexity of one-shot translational separability

✍ Scribed by Fabian Schwarzer; Achim Schweikard

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 261 KB
• Volume: 83
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(01)00333-7

✦ Synopsis

The problem of deciding whether 2-or 3-dimensional objects can be separated by a sequence of arbitrary translational motions is known to have exponential lower bounds. However, under certain restrictions on the type of motions, polynomial time bounds have been shown. An example is finding a subset of the parts that is removable by a single translation. In this case, the main restriction is that all selected parts are required to be removed in the same direction and with the same velocity. It was an open question whether the polynomial time bound can be achieved if more than a single velocity is allowed for the moving parts. In this paper, we answer this question by proving that such 'multi-handed' separability problems are NP-hard.