On the complexity of one-shot translational separability.

DOI10.1016/S0020-0190(01)00333-7MaRDI QIDQ1853067zbMATH OpenFDO

Authors Fabian Schwarzer, Achim Schweikard

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0020-0190(01)00333-7

zbMATH Keywords

Assembly planningComputational complexityComputational geometryMotion planning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 4049041
• scientific article; zbMATH DE number 4121493
• Publication:3484389
• Separating two simple polygons by a sequence of translations
• scientific article; zbMATH DE number 3883607

Cites work

• Assembly sequences for polyhedra
• Detecting geometric infeasibility
• scientific article; zbMATH DE number 3945379 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 871907 (Why is no real title available?)
• Objects that cannot be taken apart with two hands
• On Removing a Ball without Disturbing the Others
• On the complexity of assembly partitioning
• Partitioning a planar assembly into two connected parts is NP-complete

Cited in

(2)

• Objects that cannot be taken apart with two hands
• scientific article; zbMATH DE number 3883607 (Why is no real title available?)

This page was built for publication: On the complexity of one-shot translational separability.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853067)