1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – sohamb172
    Mar 1 at 9:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.