Graphics Reference
In-Depth Information
arate
X
and
Y
. The sets are said to be
strictly linearly separable
if
X
Õ i
H
(
p
,-
n
) and
Y
Õ i
H
(
p
,
n
) and the hyperplane is said to
strictly separate
X
and
Y
in this case.
Spaces that are strictly linearly separable are clearly disjoint. Spaces that are lin-
early separable may not be, but their intersection will be contained in the boundary
of the spaces if they are both n-dimensional. For example, the squares [0,1] ¥ [0,1]
and [1,2] ¥ [0,1] are linearly separable (using the hyperplane
P
((1,0),(1,0))) even
though their intersection, the line segment 1 ¥ [0,1], is nonempty.
Let
n
Œ
R
n
. If
p
Œ
R
n
, then define the
projection of
p
along
n
,
n
(
p
), by
Definition.
()
=
np
n•p
.
If
S
Õ
R
n
, then the
projection of
S
along
n
,
n
(
S
), is the subset of
R
defined by
()
=
{
()
}
nS
np p S
|
Œ
.
Note that the projection of a convex set is an interval.
Some of the results that follow have a hypothesis that certain affine hulls are n-
dimensional (for example, the set S in Theorem 17.5.1). We do this only to keep the
statement of the results as simple as possible. If the hypothesis were not to hold we
basically have a lower-dimensional problem that could also be handled easily.
17.5.1 Theorem.
Let
p
1
,
p
2
,...,
p
s
and
q
1
,
q
2
,...,
q
t
be points in
R
n
. Let
X
=
p
1
p
2
...
p
s
and
Y
=
q
1
q
2...
q
t
. Assume that the affine hull of S = {
p
1
,
p
2
,...,
p
s
,
q
1
,
q
2
,...,
q
t
}
has dimension n. The following two statements are equivalent:
(1) The convex hulls
X
and
Y
are linearly separable.
(2) There are linearly independent points
r
1
,
r
2
,...,
r
n
in S so that if
n
is any
nonzero normal vector to the hyperplane that they generate, then the inter-
vals
n
(
X
) and
n
(
Y
) intersect in at most one point.
Proof.
To show that (2) implies (1), assume that
n
(
X
) = [a,b] and
n
(
Y
) = [c,d] inter-
sect in at most one point for some vector
n
. Without loss of generality assume that b
£ c. Let
p
be a vertex of
X
so that
n
(
p
) = b. Clearly,
P
(
p
,
n
) is a separating plane for
X
and
Y
.
It remains to show that (1) implies (2). This is the nontrivial part of the theorem.
We begin by looking at the special cases of where n is 1 or 2.
Case n
=
1:
The convex hulls
X
and
Y
in this case are just intervals [a,b] and
[c,d]. We need to show that if they are linearly separable by a hyperplane
P
(
p
,
n
) (a
point in this case) then
n
(
X
) = [ka,kb] and
n
(
Y
) = [kc,kd] are either disjoint or meet
in at most one point, where k =|
n
|. This is clear.
Case n
=
2:
This is the interesting case in that its proof will show what one wants
to do in general. Suppose that
X
and
Y
are linearly separable via a line
L
=
P
(
p
,
n
). Let
e =
n
(
p
). It is easy to see that
n
(
X
) Õ (-•,e] and
n
(
Y
) Õ [e,+•), so that
n
(
X
) and
n
(
Y
)
can have at most the endpoint e in common. If
L
contains two distinct vertices from
X
and
Y
, then we are done. Otherwise, consider the case where
L
is disjoint from
X
and
