Graphics Reference
In-Depth Information
intersection volume onto the
y
axis. By picking a value for
y
from this interval and
substituting it in the original set of inequalities, a similar bound will be given for
x
,
from which a value for
x
can be chosen. The (
x
,
y
) pair of coordinates corresponds
to a feasible point in the interior of the intersection volume. Here, arbitrarily setting
y
=
2 the bounds on
x
become
−
≤
≤
≤
≤
≤
≤
7
1/2
3
x
3
17/4
8,
from which the only valid choice for
x
is
x
=
3. By inspection, Figure 9.7 has it that
(3, 2) is a vertex of the intersection volume.
Although Fourier-Motzkin elimination is both conceptually simple and straightfor-
ward to implement, a major drawback is the rapid increase of inequalities as variables
are eliminated. Worst case, the number of inequalities is squared in each iteration,
giving an exponential complexity. The situation can be improved somewhat through
heuristic rules, such as eliminating the variable producing the least number of inequal-
ities. In that most of the produced inequalities are redundant, removing these will
also curb the exponential growth, as described in [Imbert93]. Despite the worst-case
exponential complexity, Fourier-Motzkin elimination is still interesting (for small
problems) in that the method is amenable to parallelization. Fourier-Motzkin elim-
ination is closely related to a method for enumerating the vertices of a polyhedron,
known as the
double description method
[Motzkin53].
9.4.1.2 Seidel's Algorithm
A simple method for solving linear programming problems in
d
variables and
m
inequality constraints is
Seidel's algorithm
. Seidel's algorithm has an expected run-
ning time of
O
(
d
m
). Therefore, although the algorithm is not practical for large
d
it is
quite efficient for small
d
; in particular for
d
!
3, which are the dimensions of interest
for most collision detection problems. Before continuing to describe the algorithm,
the LP problem is first restated for convenience. Given is a set
≤
of
m
d
-dimensional halfspaces. The intersection of these halfspaces forms a (possibly
empty) polyhedron
P
,
P
{
H
1
,
H
2
,
...
,
H
m
}
=
H
1
∩
H
2
∩ ··· ∩
H
m
. Given is also an objective vector
d
. Wanted is a vertex
v
of
P
such that
v
is most extreme in direction
c
(or an
indication that the problem is infeasible when P is empty).
Seidel's algorithm is incremental in nature. It loops over the halfspaces and at each
iteration computes the optimum vertex
v
i
for the polyhedron
P
i
c
in
R
H
i
from
v
i
−
1
of
P
i
−
1
of the previous iteration. There are two cases to consider each time
a new halfspace
H
i
is introduced (Figure 9.8).
In the first case, when
v
i
−
1
lies inside
H
i
,
v
i
−
1
remains a feasible solution and
nothing needs to be done (thus,
v
i
=
H
1
∩
H
2
∩···∩
v
i
−
1
). On the other hand, in the case in which
v
i
−
1
lies outside
H
i
,
v
i
−
1
cannot be a feasible solution. In this case, however,
v
i
must
be contained in the bounding hyperplane
=
π
of
H
i
(because otherwise there would
