Line separates two sets of points

ignougroup
Problem Detail: 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(nlog 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.

Asked By : com

Answered By : JeffE

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1672