# What is the correct algorithm to see whether N points lie on the same side of a line?

What I tried first was to find the equation of the line and then compare its y-intercepts with the y-intercepts of each point. I just need the proper approach to this algorithm.

A quick theorem, in general:

A hyperplane in $$\mathbb{R}^d$$ can be defined by a vector $$\mathbf{v}$$ and scalar $$b$$ as the set of points $$\mathbf{x}$$ such that $$\mathbf{v}^T\mathbf{x} = b$$. It splits the space $$\mathbb{R}^d$$ up into two half-spaces, one where $$\mathbf{v}^T\mathbf{x} \geq b$$ and one where $$\mathbf{v}^T\mathbf{x} < b$$.

So in 2D, if your line is defined by $$\mathbf{v}, b$$, all you have to do is check whether either $$\mathbf{v}^T\mathbf{x} \geq b$$ or $$\mathbf{v}^T\mathbf{x} < b$$ holds for all your points $$\mathbf{x}$$.

You are probably used to a line being defined as $$y = ax + b$$. Note that we have $$\mathbf{x} = \begin{bmatrix}x\\y\end{bmatrix}$$ (beware of the bold $$\mathbf{x}$$ as opposed to $$x$$).

Thus we can rewrite to a matrix equation:

$$y = ax + b$$ $$-ax + y = b$$ $$\begin{bmatrix}-a, 1\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix} = b$$ $$\mathbf{v}^T\mathbf{x} = b$$

and we recover the above form, where $$\mathbf{v} = \begin{bmatrix}-a\\1\end{bmatrix}$$.

Thus all we have to do to check is if your points are a list of $$(x, y)$$ pairs is if either $$-ax + y \geq b$$ or $$-ax + y < b$$ for all of them.

• Hey thank you ! I didn't know anything about hyperplanes. It's fascinating that it is also a topic for ML. Now I'm much more clear. Mar 1 at 9:55