On the complexity of one-shot translational separability

Fabian Schwarzer*, Achim Schweikard

*Corresponding author for this work
1 Citation (Scopus)


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.

Original languageEnglish
JournalInformation Processing Letters
Issue number4
Pages (from-to)187-194
Number of pages8
Publication statusPublished - 31.08.2002


Dive into the research topics of 'On the complexity of one-shot translational separability'. Together they form a unique fingerprint.

Cite this