The analysis of linear constraint sets has a large number of applications. We have investigated this analysis in the context of

**Description**

The problem of finding a sequence of motions for removing one or more objects from a given set of objects arises in assembly planning, robotics, computer-aided design and pharmaceutical drug design. Given a set of parts (polygons or polyhedra), decide whether there is a motion (a sequence of arbitrary translations) for separating these parts. Conversely if you think a given set of parts interlock, output a proof that they indeed interlock.

We apply the analyis of linear constaint sets to this problem. The algorithms are based on incremental and efficient construction of cells in a high-dimensional arrangement of hyperplanes.

**Examples**

The following simple examples illustrate the translational removability problem. Given a set of parts (polygons or polyhedra), decide whether there is a motion (a sequence of arbitrary translations) for separating these parts. Conversely if you think a given set of polygons interlock, output a proof that they indeed interlock.

The animations show a series of problem examples, which
have been solved by our program. Click on the images for
animation applets.
**
**

- In each of the three cases the goal is to remove one of the two boxes from the fixed container. The first two problems are feasible, the third is infeasible.
- Here, the goal is to remove the small box from the fixed container. The bolt is restricted to move up and down in a limited range by the fixed black parts. If the bolt is too long, the problem is infeasible, which is demonstrated in the animations.
- This problem has more degrees of freedom than the others. Two parts must move simultaneously into different directions and change directions several times to allow for separation.
### Click here for more examples...

- Video.1 The parts can be separated. The computed motion and intermediate positions checked by the program are shown in the video. Compting time 12 seconds on a HP 700 Unix workstation. Video.1(218 KB).
- Video.2 The parts are similar to those in Example.1. In this case there is not removal motion. Compting time for finding a proof of infeasibility: 11 seconds. Video.2(326 KB).
- Video.3 (166 KB).
- Video.4 (105 KB).
- Video.5 (67 KB).
- Video.6 (59 KB).
- Video.7 (54 KB).