Personal tools
You are here: Home Projects In-house Projects On Two-Handed Planar Assembly Partitioning with Connectivity Constraints On Two-Handed Planar Assembly Partitioning with Connectivity Constraints
« October 2021 »
October
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31
Log in


Forgot your password?
 

On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

Abstract

hardness construction

The construction used in the hardness result.
Assembly planning aims to design a sequence of motions that brings 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 that each of the two subassemblies will be connected.
 
In this paper we study a natural special case of the connected-assembly-partitioning problem: Given a connected set 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.
 
We show that even this simple problem is NP-complete, settling an open question posed by Wilson et al. (1995) a quarter of a century ago. We complement the hardness result with two positive results. First, we show that it is fixed-parameter tractable and give an O(2kn2)-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. 


Links

Contacts

Tzvika Geft http://acg.cs.tau.ac.il/people/tzvika-geft/tzvika-geft null
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Document Actions