algorithmgeometryinequalities

How to code check if system of inequalities has a solution

I need to find algorithm that can check if system like this

x1 * k + b > y1, x2 * k + b > y2, ..., xn * k + b < yn

has solution(s) where i substitute x[i] and y[i] and unknown varialbes are k,b.

Solution

  • You question is equivalent to asking if the points are linearly separable (with one class of points corresponding to the inequalities with >, the others with <).

    You can use the Perceptron Algorithm to find a separating line if one exists. That wikipedia page provides some alternative algorithms too.