Line separates two sets of points

If there is a way to identify if two sets of points can be separated by a line?


We have two sets of points $A$ and $B$ if there is a line that separates $A$ and $B$ such that all points of $A$ and only $A$ on the one side of the line, and all points of $B$ and only $B$ on the other side.

The most naive algorithm I came up with is building convex polygon for $A$ and $B$ and test them for intersection. It looks time the time complexity for this should be $O(n\log h)$ as for constructing a convex polygon. Actually I am not expecting any improvements in time complexity, I am not sure it can be improved at all. But al least there should be a more beautiful way to determine if there is such a line.

Both uli and Dave Clarke correctly observe that this is a linear programming problem, even in higher dimensions (Can these two point sets be separated by a hyperplane?) and so it can be solved in polynomial time. But because your points lie in the plane, your problem can actually be solved in $O(n)$ time, where $n$ is the total number of points.

The simplest solution is probably Seidel's randomized algorithm. Choose an input point $p$ uniformly at random, and recursively compute a separating line $\ell$ for all the points except $p$.

-
If no such line exists, then the original points are not separable.

-
If $p$ is on the correct side of $\ell$, then $\ell$ separates the original points.

-
If $p$ is on the wrong side of $\ell$, then either the original points can be separated by a line through $p$, or the original points are not separable at all. This condition is easy to check in $O(n)$ time [exercise].

This algorithm runs in $O(n)$ time with high probability (with respect to the algorithm's random choices). For more details, see the original paper or any number of online lecture notes.

StackExchange Computer Science Q#1672, answer score: 19