  We first prove a new separating hyperplane theorem characterizing when a pair
of compact convex subsets $K, K'$ of the Euclidean space intersect, and when
they are disjoint. The theorem is distinct from classical separation theorems.
It generalizes the {\it distance duality} proved in our earlier work for
testing the membership of a distinguished point in the convex hull of a finite
point set. Next by utilizing the theorem, we develop a substantially
generalized and stronger version of the {\it Triangle Algorithm} introduced in
the previous work to perform any of the following three tasks: (1) To compute a
pair $(p,p') \in K \times K'$, where either the Euclidean distance $d(p,p')$ is
to within a prescribed tolerance, or the orthogonal bisecting hyperplane of the
line segment $pp'$ separates the two sets; (2) When $K$ and $K'$ are disjoint,
to compute $(p,p') \in K \times K'$ so that $d(p,p')$ approximates $d(K,K')$ to
within a prescribed tolerance; (3) When $K$ and $K'$ are disjoint, to compute a
pair of parallel supporting hyperplanes $H,H'$ so that $d(H,H')$ is to within a
prescribed tolerance of the optimal margin. The worst-case complexity of each
iteration is solving a linear objective over $K$ or $K'$. The resulting
algorithm is a fully polynomial-time approximation scheme for such important
special cases as when $K$ and $K'$ are convex hulls of finite points sets, or
the intersection of a finite number of halfspaces. The results find many
theoretical and practical applications, such as in machine learning,
statistics, linear, quadratic and convex programming. In particular, in a
separate article we report on a comparison of the Triangle Algorithm and SMO
for solving the hard margin problem. In future work we extend the applications
to combinatorial and NP-complete problems.
