On the complexity of assembly partitioning. (English) Zbl 0787.68050

Summary: We study the complexity of the assembly partioning 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.


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


[1] Arkin, E. M.; Connelly, R.; Mitchell, J. S.B., On monotone paths among obstacles with applications to planning assemblies, Proc. 5th ACM Symp. on Computational Geometry, 334-343 (1989)
[2] Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[3] Guibas, L.; Yao, F., On translating a set of rectangles, (Preparate, F. P., Computational Geometry, 1 (1983), JAI Press: JAI Press London), 61-67, Advances in Computing Research
[4] Halberstam, H.; Roth, K. F., Sequences (1983), Springer: Springer New York · Zbl 0498.10001
[5] de Mello, L. S.Homem; Lee, S., Computer-Aided Mechanical Assembly Planning (1991), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA
[6] Kavraki, L.; Latombe, J.-C., Complexity of partitioning a planar assembly, Tech. Rept. STAN-CS-93-1467 (1993), Dept. of Computer Science, Stanford University
[7] Natarajan, B. K., On planning assemblies, Proc. 4th ACM Symp. on Computational Geometry, 299-308 (1988)
[8] Nussbaum, D.; Sack, J. R., Dissasembling two-dimensional composite parts via translations, Internat. J. Comput. Geom., 3, 71-84 (1993) · Zbl 0777.68081
[9] Pollack, R.; Sharir, M.; Sifrony, S., Separating two polygons by a sequence of translations, Discrete Comput. Geom., 3, 123-136 (1988) · Zbl 0646.68052
[10] Schwartz, J. T.; Sharir, M., On the piano movers’ problem: I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers, Comm. Pure Appl. Math., 36, 345-398 (1983) · Zbl 0554.51007
[11] Snoeyink, J.; Stolfi, J., Objects that cannot be taken apart with two hands, Proc. 9th ACM Symp. on Computational Geometry, 247-256 (1993) · Zbl 0813.52004
[12] Toussaint, G. T., Movable separability of sets, Computational Geometry (1985), North-Holland: North-Holland Amsterdam · Zbl 0588.68053
[13] Wilson, R. H., On geometric assembly planning, Ph.D. Thesis (March 1992), Stanford University, Tech. Rept. STAN-CS-92-1416
[14] Wilson, R. H.; Latombe, J. C.; Lozano-Pérez, T., On the complexity of partitioning an assembly, Tech. Rept. STAN-CS-92-1458 (1992), Dept. of Computer Science, Stanford University
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.