The analysis of linear constraint sets has a large number of applications. We have investigated this analysis in the context of
Testing for Removability (Joint work with Leo Joskowicz, Hebrew University, Jerusalem)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.
MPEG videos are available for some examples:
Click here for
more examples...