Personal tools
You are here: Home CG seminar 2020 Partitioning an Assembly into Two Connected Subassemblies is NP-Complete even for Single Translation of Unit Squares
« September 2020 »
September
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
27282930
Log in


Forgot your password?
 

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

underline

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.  
 
Joint work with Pankaj K. Agarwal, Boris Aronov, and Dan Halperin.
 

Recordings:

First minute: here
The rest: here
Document Actions