Learning triangles in the plane I assigned my students the problem of finding a triangle consistent with a collection of $m$ points in $\mathbb{R}^2$, labeled with $\pm1$. (A triangle $T$ is consistent with the labeled sample if $T$ contains all of the positive and none of the negative points; by assumption, the sample admits at least 1 consistent triangle).

The best they (or I) could do is an algorithm that runs in time $O(m^6)$, where $m$ is sample size. Can anyone do better?
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.