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 finding the point with the largest Eucledean 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 Eucledean 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 Eucledean distance, so I'm quiet baffled as to how it is supposed to work, if this method even works..

$\endgroup$

1 Answer 1

3
$\begingroup$

If the triangle is centered at the origin, in general only one point touches it. You find this point as the one furthest in the three directions normal to the triangle sides (by taking the dot product with the normal vectors). As there are three distances, you take the largest.

Beware that the relevant distance is not the Euclidean distance to the center.

$\endgroup$
5
  • $\begingroup$ Hi, thanks for the reply! I'm a bit confused about the definition of relevant distance as oppose to Eucledean distance.. can you explain? $\endgroup$ May 27, 2022 at 15:10
  • $\begingroup$ @MathCurious Distance to a line. $\endgroup$
    – user16034
    May 27, 2022 at 15:49
  • $\begingroup$ So you're saying to create a triangle you need to take the dot product with the normal vectors, u,w and v in our case and then to take the largest r value? So it is unneccesary to first find the point fathest away from the eucledean distance, and instead we need to go over all points, for every one make the dot product calculation and store the highest result into r, and overall we take the biggest r we found? $\endgroup$ May 27, 2022 at 16:23
  • $\begingroup$ @MathCurious: it is no use to compute the Euclidean distance. $\endgroup$
    – user16034
    May 27, 2022 at 19:23
  • $\begingroup$ I got it, thank you very much! $\endgroup$ May 28, 2022 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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