Graphics Reference
In-Depth Information
Figure 17.7.
Determining a separating plane.
Y
. (It will be obvious from the discussion of this case how to deal with the other case
where
L
contains one vertex from
X
and
Y
.) See Figure 17.7. Consider the distances
from the vertices of
X
and
Y
to
L
. Assume without loss of generality that it is a vertex
r
1
of
X
that is closest to
L
. Let
L
¢ be the line through
r
1
that is parallel to
L
. Clearly,
L
¢
linearly separates
X
and
Y
. If
L
¢ contains no vertex of
X
other than
r
1
, then rotate
L
¢
about
r
1
through an angle q to a line
L
≤ that “bumps” into another vertex of
X
or
Y
other
than
r
1
. We can let this vertex be
r
2
. See Figure 17.7, where
r
2
belongs to
X
. For the
angle of rotation simply take the minimum of all the angles between
L
¢ and lines
through
r
1
and a vertex of
X
or
Y
. (To have well-defined angles orient the line
L
¢.)
The General Case.
This case is handled similar to the case where n is 2. Instead
of lines we now have hyperplanes. If the separating hyperplane is disjoint from
X
and
Y
, then we translate it to pass through a point of
X
. Finally, we rotate it about this
point, if necessary, until we have “bumped” into n linearly independent vertices of
X
and
Y
.
The theorem is proved.
In the special case where
Y
is a point, we can strengthen the result in Theorem
17.5.1.
17.5.2 Theorem.
Let
p
1
,
p
2
,...,
p
s
, and
q
be points in
R
n
. Assume that
X
=
p
1
p
2
...
p
s
has dimension n. Then
q
is disjoint from
X
if and only if there is a subset
{
r
1
,
r
2
,...,
r
n
} of linearly independent points of {
p
1
,
p
2
,...,
p
s
} so that the hyperplane
H
= aff({
r
1
,
r
2
,...,
r
n
}) strictly separates
X
and
q
.
Proof.
Since the point
q
is clearly disjoint from
X
if the hyperplane
H
exists, we
only need to prove the converse. If
q
does not belong to
X
, we know that we can
strictly separate
X
and
q
by a hyperplane
P
(
p
,
n
). By translating
P
(
p
,
n
), if necessary,
we may assume like in the proof of Theorem 17.5.1 that
p
is a vertex of
X
. Consider
the (n - 1)-dimensional faces of
X
that contain
p
and let
P
(
p
,
n
1
),
P
(
p
,
n
2
),...,
P
(
p
,
n
m
) be the hyperplanes determined by these faces, where the normals
n
i
are
