On the Complexity of Assembly Partitioning

L. E. Kavraki, J.-C. Latombe, and R. H. Wilson, “On the Complexity of Assembly Partitioning,” Information Processing Letters, vol. 48, no. 5, pp. 229–235, 1993.


This paper studies the complexity of the assembly partitioning problem in the plane: given a collection of non-overlapping polygons, decide if there is a proper subcollection of them that can be removed as a rigid body without colliding with or disturbing the other parts of the assembly. It is shown that assembly partitioning is NP-complete. The result extends to several interesting variants of the problem.

Publisher: http://dx.doi.org/10.1016/0020-0190(93)90085-N

PDF preprint: http://kavrakilab.org/publications/kavraki-latombe1993on-complexity-of.pdf