Line separates two sets of points

Question

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.

Answer 1

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.

Answer 2

The property of your two data sets is that of linear separability, simply, that there is a line that separates them. A lot of machine learning is devoted to finding linear classifiers, which are lines that perform the separation you are interested in.

As you are talking about lines, I'll assume that your points lie in the plane. What you want to do is find values $w_1$, $w_2$ and $w_3$, such that for all points $(a_1,a_2)$ in set $A$, $w_1 a_1+w_2a_2\ge w_3$ and for all points $(b_1,b_2)$ in $B$, $w_1 b_1+w_2b_2<w_3$. Thus, the inequality $w_1 x+w_2y\ge w_3$ can be seen as a classifier for set $A$.

There are loads of machine learning algorithms for determining an optimal line (linear regression, logistic regression, and so forth). These will find values for $w_1,w_2,w_3$ based on some error metric. Then you can test whether all of the points are correctly classified. That is, whether all of the values in $A$ satisfy the equation above and similarly for $B$.

As you are only interested in whether such a line exists, you needed use existing techniques (though that probably would be simpler). Simply set up the following collection of equalities in terms of free variables $w_1,w_2,w_3$.

$w_1 a^i_1+w_2a^i_2\ge w_3$ for each $i=1,..,|A|$, where $A=\{(a^1_1,a^1_2),\ldots,(a^{|A|}_1,a^{|A|}_2)\}$.

$w_1 b^j_1+w_2b^j_2< w_3$ for each $j=1,..,|B|$, where $B=\{(b^1_1,b^1_2),\ldots,(b^{|B|}_1,b^{|B|}_2)\}$.

If these constraints are consistent, then a line exists.

Answer 3

If I remember correctly support vector machines construct seperating hyperplanes. If you choose dimension $2$ the hyperplane becomes of course a line. You might have to check if there are additional assumptions to be met. In two dimensions the whole approach might simplify considerably so the runtime might be better than for the general approach.