Graphics Reference
In-Depth Information
minimizing) a linear function with respect to a finite set of linear constraints. The
linear function to be optimized is called the
objective function
. Without loss of gener-
ality, linear programming (LP) problems are here restricted to maximization of the
objective function and to involve constraints of the form
f
(
x
1
,
x
2
,
...
,
x
n
)
≤
c
only
(because
f
(
x
1
,
x
2
,
...
,
x
n
)
c
). Equality
constraints, if needed, can be stated by requiring both
f
(
x
1
,
x
2
,
...
,
x
n
)
≥
c
can be written as
−
f
(
x
1
,
x
2
,
...
,
x
n
)
≤−
≤
c
and
f
(
x
1
,
x
2
,
...
,
x
n
)
c
.
Note that a linear inequality of
n
variables geometrically defines a halfspace in
≥
n
. The region of feasible solutions defined by a set of
m
inequalities therefore cor-
responds to the intersection of
m
halfspaces
H
i
,1
R
≤
i
≤
m
. In turn, this intersection
corresponds to a convex polyhedron
P
,
P
H
m
. Note also that the
objective function can be seen as a dot product between the vectors
x
=
H
1
∩
H
2
∩
...
∩
=
(
x
1
,
x
2
,
...
,
x
n
)
and
c
(
c
1
,
c
2
,
...
,
c
n
). The LP problem is therefore geometrically equivalent to that
of finding a supporting point
x
of
P
in direction
c
. (In fact, because
P
is a convex poly-
hedron the supporting point
x
can always be made to correspond to a supporting
vertex.)
In the literature, LP problems are often abstractly stated in terms of matrix-vector
formulations, rather than as a geometric optimization over a convex polyhedron.
In a matrix formulation the LP problem is to maximize (or minimize) the objective
function
c
T
x
, where
c
is a (column) vector of
d
constants and
x
=
(
x
1
,
x
2
,
...
,
x
d
)
T
=
≤
×
satisfies the constraint inequalities
Ax
d
matrix of coefficients
and
b
is a column vector of
n
constants). The geometric interpretation is preferred in
this topic.
Given two convex polyhedra,
A
and
B
, each expressed as the intersection of half-
spaces, the convex polyhedron
C
that is their intersection volume is described
(perhaps redundantly) by the intersection of all halfspaces from both
A
and
B
.
A
and
B
are therefore in collision if and only if there is a solution to the LP problem
with the defining halfspaces of
A
and
B
as the linear constraints. Because any point
common to both polyhedra will serve as a witness to their collision, the objective
function can be chosen arbitrarily, for example as
c
b
(where
A
is an
n
(1, 0,
...
, 0).
As an example of how polyhedral intersection can be treated as an LP problem,
consider the two triangles,
A
and
B
, given in Figure 9.7. Triangle
A
is described by
the halfspaces
=
−
x
+
y
≤−
1,
−
x
−
4
y
≤−
1, and 4
x
+
y
≤
19, and triangle
B
by
the halfspaces
−
4
x
+
y
≤
0,
x
−
4
y
≤
0, and
x
+
y
≤
5. The triangles are therefore
intersecting if the following LP problem has a solution.
Maximize
x
subject to:
−
x
+
y
≤−
1
−
x
−
4
y
≤−
1
4
x
+
y
≤
19
−
+
≤
4
x
y
0
