Deleting nodes from graph so that they can be separated by a straight line

Question

I have 2 types of points in a 2D plane, type 'A' and type 'B'. How do I delete the minimum possible number of points so that remaining can be separated (on different sides) by a straight line.

I tried modeling this as a graph, where I have 2 types of nodes, and i delete nodes from it. But I can't formulate an algorithm.

How can I go about formulating an algorithm for this situation?

Answer 1

Try the following (inefficient) approach. Assume there are $N$ points in total. Now with each of the $N$ points try to find a line segment that passes through it with the least number of mis-classifications (number of points that were not correctly separated) by the line segment. The important point to note here is that, you would not have more than $N-1$ such line segments to check for. At the end of the procedure simply choose the point and its best corresponding line segment. The overall complexity is $O(N^3)$ under ideal conditions. Some perturbation of point may be required in the process, if not ideal.

A slightly more efficient procedure is as follows, let the convex hull of the points in type 1 be $P_1$ and those of type 2 be $P_2$. Then I suspect, in the previous procedure, instead of computing the best line segment for every point, just do the procedure for those in $P_1 \cap P_2$.

Answer 2

There are loads of machine learning algorithms for determining an optimal line (linear regression, logistic regression, and so forth). These will find values for w1,w2,w3 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 w1,w2,w3

.

w1ai1+w2ai2≥w3 for each i=1,..,|A|, where A={(a11,a12),…,(a|A|1,a|A|2)}

.

w1bj1+w2bj2

.

If these constraints are consistent, then a line exists.