linear separability test.

[Stephen M. Omohundro]

A couple of simple transformations will convert the linear
separability question from intersection of two convex hulls to just
the containment of a point in a single convex hull. First realize that
we can focus attention just on hyperplanes through the origin by
embedding the original problem in the "z=1" plane one dimension
higher. Each arbitrary hyperplane in the original problem then
corresponds to a hyperplane through the origin in this bigger space.
Consider the unit vector v which is perpendicular to such a plane. The
plane is separating if the dot product of this vector with each point
in set1 is negative and with each point in set2 is positive. If we
reflect a point through the origin (ie. (x1,...,xn) -> (-x1,...,-xn))
then the sign of its dot product with any vector also changes. Thus if
we do such reflection on each point in set1, we have reduced the
problem to finding a vector whose dot product with each of a set of
points is positive. The existence of such a vector is equivalent to
the origin not being included in the convex hull of the points.

--Stephen Omohundro