Graphics Reference
In-Depth Information
A: -
x
+
y
-1
-
x
- 4
y
-1
4
x
+
y
19
B
B: - 4
x
+
y
0
x
- 4
y
0
x
+
y
5
A
Figure 9.7
The two triangles
A
= (1, 0), (5, −1), (4, 3) and
B
= (0, 0), (4, 1), (1, 4) defined
as the intersection of three halfspaces each.
x
−
4
y
≤
0
x
+
y
≤
5
By inspection of Figure 9.7, this problem has a solution, with the maximum assumed
for
x
4.
Alternatively, the intersection problem can be expressed as an LP problem in the
following way. Let the two polyhedra be given in terms of their vertices. Now a linear
programming problem can be set up to determine whether there exist coefficients for
a plane such that it forms a separating plane for the two polyhedra. For example, for
the setup of Figure 9.7 the problem can be restated to attempt to find a separating
line
f
(
x
,
y
)
=
=
ax
+
by
+
c
for some
a
,
b
, and
c
with the constraints that
f
(
A
i
)
≤
0 and
f
(
B
i
)
0, where
A
i
and
B
i
are the vertices of the two polyhedra. Specifically, for the
setup of Figure 9.7 the two triangles are nonintersecting if the following LP problem
has a solution.
>
Maximize
a
+
≤
subject to:
a
c
0
−
+
≤
5
a
b
c
0
4
a
+
3
b
+
c
≤
0
c
>
0
4
a
+
b
+
c
>
0
a
+
4
b
+
c
>
0
In that it is already established that triangles
A
and
B
are intersecting, this
particular LP problem does not have a solution.
