# Partitioning an Assembly into Two Connected Subassemblies is NP-Complete even for Single Translation of Unit Squares

### Wednesday, May 13th, 2020, 16:10

~~Checkpoint 480~~

### Zoom: Request the link from Dan Halperin or Golan Levy

### Partitioning an Assembly into Two Connected Subassemblies is NP-Complete even for Single Translation of Unit Squares

### Tzvika Geft, TAU

### Abstract:

Assembly planning 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 (sliding of one subassembly over the other, namely motion in contact, is allowed). 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 that each of the two subassemblies will be connected.

In this paper we show that even an utterly simple variant of the connected-assembly-partitioning problem is hard: Given a connected set A of unit squares in the plane, each contained in a distinct cell of a uniform grid, find a subset S of A that can be rigidly translated to infinity along a prescribed direction, such that both subassemblies S and A\S are each connected, and such that S does not collide with A\S throughout the motion. We show that this problem is NP-Complete, and by that settle a long-standing open problem posed by Wilson et al (1995) a quarter of a century ago. This motivates us to look for efficient solutions in special cases, which we describe here as well.