# Linear separability

I have an assignment in linear programming and this question was asked: given an input of two data sets $$P_1,P_2$$ containing points $$(x,y)$$, create a linear program that finds an equation of a line the separates between the two data sets.

Now I saw in Wikipedia the article about linear separability and I didn't understand what are the variables of $$w_1,w_2,\ldots,w_n$$ stand for, and why does their algorithm work. If anyone could clarify this for me it would be great.

The general equation of a line in the plane is $$ax + by = c.$$ (The equation $$y = ax + b$$ cannot handle vertical lines.) This line separates the plane into two parts: those satisfying $$ax+by > c$$, and those satisfying $$ax+by < c$$. Your two datasets are linearly separable if there exist $$a,b,c$$ such that all points in $$P_1$$ satisfy $$ax+by > c$$, and all points in $$P_2$$ satisfy $$ax+by < c$$. (If all points in $$P_1$$ satisfy $$ax+by and all points in $$P_2$$ satisfy $$ax+by>c$$, then we can negate $$a,b,c$$ to get to the situation above.)
In order to find $$a,b,c$$ using linear programming, we need to replace the strict inequalities $$>,<$$ with non-strict inequalities $$\ge,\le$$. The idea is the for small enough $$\epsilon>0$$, the points in $$P_1$$ would actually satisfy $$ax+by \geq c+\epsilon$$, and the points in $$P_2$$ would satisfy $$ax+by \leq c-\epsilon$$. While we don't know $$\epsilon$$, if we multiply the two inequalities by $$1/\epsilon$$, we effectively make $$\epsilon$$ equal to $$1$$. Therefore we look for $$a,b,c$$ such that $$ax+by \geq c+1$$ for all points in $$P_1$$, and $$ax+by \leq c-1$$ for all points in $$P_2$$. This is a linear program, which can be solved using standard algorithms.