0
$\begingroup$

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. enter image description here

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:

enter image description here

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..

$\endgroup$

1 Answer 1

2
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ Perfect, thank you! $\endgroup$ May 31 at 4:59

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.