Assembly planning, which is a fundamental problem in robotics and automation, aims to design a sequence of motions that will bring the separate constituent parts of a product into their final placement in the product. It is convenient to study assembly planning in reverse order, where the following key problem, *assembly **partitioning*, arises: Given a set of parts in their final placement in a product, partition them into two sets, each regarded as a rigid body, which we call a subassembly, such that these two subassemblies can be moved sufficiently far away from each other, without colliding with one another. The basic assembly planning problem is further complicated by practical consideration such as how to hold the parts in a subassembly together. Therefore, a desired property of a valid assembly partition is for each of the two subassemblies to be connected.

We previously showed that even the following simple case of the connected-assembly-partitioning problem is NP-complete: Given a connected set A of unit grid squares in the plane, find a connected subset S of A such that A\S is also connected and S can be rigidly translated to infinity along a prescribed direction without colliding with A\S.

In this talk the previous hardness result will be complemented with two positive results for the aforementioned problem variant for grid square assemblies.

First, we show that it is fixed parameter tractable and give an O(2^k n^2)-time algorithm, where n=|A| and k=|S|. Second, we describe a special case of this variant where a connected partition can always be found in linear time. Each of the positive results sheds further light on the special geometric structure of the problem at hand.

To appear in SODA 2021.

Joint work with Pankaj K. Agarwal, Boris Aronov, and Dan Halperin.