# On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

arXiv: https://arxiv.org/abs/2009.12369 · HTML: https://mlsanity.com/paper/2009.12369/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Sep 2020.

## Built on by (most cited first, 1 of 1)

- [Fine-Grained Complexity Analysis of Multi-Agent Path Finding on 2D Grids](https://mlsanity.com/paper/2305.16303/) (2023)

## Abstract (arXiv)

Assembly planning is a fundamental problem in robotics and automation, which involves designing a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, giving rise to the assembly partitioning problem: Given a set A of parts, find a subset Ssubset A, referred to as a subassembly, such that S can be rigidly translated to infinity along a prescribed direction without colliding with Asetminus S. While assembly partitioning is efficiently solvable, it is further desirable for the parts of a subassembly to be easily held together. This motivates the problem that we study, called connected-assembly-partitioning, which additionally requires each of the two subassemblies, S and Asetminus S, to be connected. We show that this problem is NP-complete, settling an open question posed by Wilson et al. (1995) a quarter of a century ago, even when A consists of unit-grid squares (i.e., A is polyomino-shaped). Towards this result, we prove the NP-hardness of a new Planar 3-SAT variant having an adjacency requirement for variables appearing in the same clause, which may be of independent interest. On the positive side, we give an O(2k n2)-time fixed-parameter tractable algorithm (requiring low degree polynomial-time pre-processing) for an assembly A consisting of polygons in the plane, where n=|A| and k=|S|. We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in O(n)-time.