Finding the tightest (smallest) triangle that fits all points

I'm supposed to find an algorithm that, given a bunch of points on the Euclidean plane, I have to return the tightest (smallest) origin centered upright equilateral triangle that fits all the given points inside of it, in a way that if I input some random new point, the algorithm will return $+$ if the point is inside the triangle and $-$ if not.

Someone has suggested me to go over all the possible points and find the point with the largest Euclidean distance from the origin, then, say the point is $(x_1,x_2)$, I should calculate the following:

$(x_1,x_2)⋅(\frac{\sqrt{3}}{2},-\frac{1}{2})=x_{1}\cdot\frac{\sqrt{3}}{2}+x_{2}\cdot-\frac{1}{2}=r_{1}$

$(x_1,x_2)⋅(-\frac{\sqrt{3}}{2},-\frac{1}{2})=x_{1}\cdot-\frac{\sqrt{3}}{2}+x_{2}\cdot-\frac{1}{2}=r_{2}$

$(x_1,x_2)⋅(0,1)=x_{1}\cdot0+x_{2}\cdot1=r_{3}$

Then take the maximum of $r_1,r_2,r_3$, denote it $r_{max}$ and given a new random point $(y_1,y_2)$ output $+$ if

$(y_1,y_2)⋅(\frac{\sqrt{3}}{2},-\frac{1}{2})\le r_{max}$

$(y_1,y_2)⋅(\frac{\sqrt{3}}{2},-\frac{1}{2})\le r_{max}$

$(y_1,y_2)⋅(0,1)\le r_{max}$

It should look something like this:

and output this triangle:

Now when I try to graph points with the same Euclidean distance on a graph, they do indeed seem to be on the sides of the same origin centered upright equilateral triangle, but I can get different $r$ values for different points which have the same Euclidean distance, so I'm quiet baffled as to how it is supposed to work, if this method even works..

Topic pac-learning algorithms machine-learning

Category Data Science


There appear to be a few issues with this approach.

  1. In the second step you have $(y_1,y_2)⋅(\frac{\sqrt{3}}{2},-\frac{1}{2})≤r_{max}$ twice. Presumably one of these should be $(y_1,y_2)⋅(-\frac{\sqrt{3}}{2},-\frac{1}{2})≤r_{max}$.
  2. The vectors you have used give you an upside-down triangle, not an upright one.
  3. Points with the same Euclidean distance from the origin form a circle. So you get a different enclosing triangle (so hence a different value for $r$) depending on whereabouts on the circle the point is. There is no need to calculate the Euclidean distance for each point. Try finding $r_{max}$ for each point, then select the most appropriate $r_{max}$ instead.

About

Geeks Mental is a community that publishes articles and tutorials about Web, Android, Data Science, new techniques and Linux security.