Learning triangles in the plane
As @TsuyoshiIto suggests, there is an $O(n\log n)$-time algorithm for this problem, due to Edelsbrunner and Preparata.  In fact, their algorithm finds a convex polygon with the minimum possible number of edges that separates the two point sets.  They also prove an $\Omega(n\log n)$ lower bound for the more general problem in the algebraic decision tree model; however, it's not clear whether this lower bound applies to the triangle case.

A full description of the algorithm is too long to post here, but here's the basic idea.  Let $C$ be the convex hull of the positive points.  For each negative point $q$, consider the lines through $q$ that are tangent to $C$.  These lines split the plane into four wedges, one of which contains $C$; let $W(q)$ be the wedge opposite the one that contains $C$.  Finally, let $F$ (the "forbidden region") be the union of all wedges $W(q)$.  Any separating triangle must separate $C$ from $F$.  Both $C$ and $F$ can be constructed in $O(n\log n)$ time.



Label the edges of $F$ alternately clockwise and counterclockwise.  Edelsbrunner and Preparata further prove that if a separating triangle exists, then there is a separating triangle whose edges are collinear with clockwise edges of $F$.  In $O(n)$ additional time, we can find the (necessarily clockwise) edge of $F$ first hit by a ray from each clockwise edge $e$; call this edge the "successor" of $e$.  The successor pointers partition the clockwise edges into cycles; if there is a separating triangle, one of these successor cycles has length 3 (and none have length more than 4).

See the original paper for more details:


Herbert Edelsbrunner and Franco P. Preparata.  Minimum polygonal separation.  Information and Computation 77(3):218–232, 1988.