On the complexity of one-shot translational separability |
| |
Authors: | Fabian SchwarzerAchim Schweikard |
| |
Affiliation: | Informatik, Technische Universität München, 80290 München, Germany |
| |
Abstract: | 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. |
| |
Keywords: | Computational complexity Computational geometry Assembly planning Motion planning |
本文献已被 ScienceDirect 等数据库收录! |