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

**Example:** (Click here for
an animation of another example)

The two parts below consist of 300 and 588 surface
triangles. Thus 176400 pairs of triangles must be prevented
from interpenetration. By a sequence of hierarchical
filters we can substantially reduce the number of pairs that
must actually be considered for a specific class of
configurations.

We consider the following configuration (the second part is
shown transparent):

The next figure shows the computed cell that is a subset of
free C-Space. It contains the origin which represents the
given configuration.
The cell is defined by the intersection of 17 halfspaces.
16 of them form a channel parallel to the z-axis and one
delimits it in negative z direction. The program directly
computes the set of defining halfspace-inequalities in the
form **ax + by + cz >= d** which can be used for further
analysis (e.g. C-Space composition, see Testing for
Removability for more details on this topic).

The cell is unbounded in positive z direction which means that the second part can translate to infinity along the positive z axis. Along the negative z-axis, however, there is only a finite volume of free C-Space since the parts will collide during a translation of the second part in this direction.

The channel has non-zero diameter which indicates play
between the parts in x- and y-directions.

The next figure shows a cross section of the cell at some
positive z-value.

In the example we can additionally compute a convex cone of free directions. Each vector in the cone specifies a direction in which the second part can be translated arbitrarily far away from the first part. The next two figures show the cell from the previous figures and the computed cone of allowed translations to infinity. Note that the set of all allowed directions need not be convex for all configurations (consider a placement in which the two parts can be separated by a plane).