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.
Line separates two sets of points
algorithms;machine learning;computational geometry
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.