2
$\begingroup$

Considering the image below, I want to compute the smallest triangle T enclosnging all the points in the set of vertices in a convex polygon. I have an iterative algorithm doing the job based on the assumption that the each edge of T is a superset to some edge of the convex polygon. That assumption turned out to be wrong. Two of the edges of T must be supersets to precisely two of the polygon's edges. However, apparently, it's possible that the third edge of T might be tangenting a vertex of the polygon, hence only intersecting a single vertex of it, instead of two. (The difference in large sets of points is insignificant and I've missed that. Shame on me!)

How can I find the correct tangent (that might turn out to be a superset to an edge of the polygon)?

enter image description here

In the image above, I can easily exclude

  • c becuase neither cb' nor ca produces an enclosing triangle,
  • d because de has the same slope as bb' and da' doesn't produce a triangle at all
  • g because gb doesn't produce triangle at all and gf produces a triangle that isn't minimal

So we've got the candidates of e and f but the triangle produced by ef doesn't need to be the minimal one (that was my mistake to believe). The correct line that minimizes the triangle will pass through e or f (or both), though.

How can I compute that line?

enter image description here

I have suspicion that the correct line must be perpendicular to the mid-angular line that passes through the intersection of aa' and bb' (hence having the same angle to the former as to the latter). If I have that slope, I only need to offset it so that it passes through each of the candidates and compare the sizes of produces triangles.

Is that a correct approach or am I missing a flaw somewhere? I'm not making an ass of myself again.

$\endgroup$
  • $\begingroup$ Smallest triangle in terms of area ? $\endgroup$ – Jean Marie Sep 3 '16 at 10:28
  • 1
    $\begingroup$ Look at the second answer here: stackoverflow.com/questions/22441855/… $\endgroup$ – bubba Sep 3 '16 at 10:29
  • $\begingroup$ The "mid-angular" line is not the correct line in general. You are looking for a minimal area triangle that goes through $f$. So among green lines through $f$, you want the one giving the smallest product for the two orange sides. This will be the one having $f$ as its midpoint. You can see this by considering a linear transformation that maps the orange lines into the $x$ and $y$ axis and puts $f$ at $(1,1)$. You can also see this from physics, since external air pressure on the green line will make it rotate around $f$ until it is balanced, which happens when $f$ is the midpoint. $\endgroup$ – Matt Sep 3 '16 at 10:52
  • $\begingroup$ @bubba: Not the same problem. In that problem one has to choose all three sides. $\endgroup$ – mathreadler Sep 3 '16 at 10:52
  • $\begingroup$ @mathreadler: It looks like it is exactly the same problem. It looks to me like the question here draws the figure this way only due to the conclusion that "Two of the edges of T must be supersets to precisely two of the polygon's edges." $\endgroup$ – Matt Sep 3 '16 at 11:01
1
$\begingroup$

If you want to find the triangle which is smallest by area (is this what you want?) (as opposed to smallest perimeter, smallest diameter, smallest circumcircle, etc.), and the two orange lines are already given (are they? if not, see here), then it can be solved like this:

For each of the points $d, e, f, g$ you can compute the minimal area triangle among triangles where the third side goes through that point. Call the two orange lines $M$ and $N$. The minimal area triangle through $e$, for example, is formed by a green line $L$ that meets $M$ at a point which is twice as far from $N$ as $e$ is, and meets $N$ at a point which is twice as far from $M$ as $e$ is. In other words, $e$ is the midpoint of the green side of the triangle. In other words, if you draw a parallelogram with sides on $M$ and $N$ and a vertex at $e$, then the triangles sides on $M$ and $N$ are each twice as long as the parallelogram's.

Why is this the minimal-area triangle? Among green lines through $f$, you want the one giving the smallest product for the two orange sides. This will be the one having $f$ as its midpoint. You can see this by considering a linear transformation that maps the orange lines into the $x$ and $y$ axes and puts $f$ at $(1,1)$. You can also see this from physics, since external air pressure on the green line will make it rotate around $f$ until it is balanced, which happens when $f$ is the midpoint.

Ok, so for each individual point, we can find the minimal-area triangle. If any of these triangles encloses all the points (at most one can), then it is the minimal triangle, and we are done. Otherwise, each triangle leaves out either the preceding point or the following point, but not both (due to the convexity of the polygon of the points). At the place where this transitions from "following" to "preceding", we must place the third triangle side on those two points. For example, in the diagram shown, the best triangle through $e$ leaves out $f$, while the best triangle through $f$ just barely leaves out $e$, so the best triangle enclosing both $e$ and $f$ has its third side passing through $e$ and $f$.

$\endgroup$
  • $\begingroup$ On one hand, I'm happy because you provided me with some awesome help. On the other hand, I'm PO'ed because the contents of the help need to be implemented in C# and it's complicated and tedious AF. So I have a very mixed set of emotions towards geometry (and I'm a M.Sc. in math for the love of a higher deity, be that many years ago but still...). All in all, +1 and huge thanks, mate. $\endgroup$ – Konrad Viltersten Sep 3 '16 at 12:01
0
$\begingroup$

Here's an idea which maybe partially solves the problem.

  1. Draw vectors along the two first determined sides, from their corner.
  2. Project each point in the triangle onto those vectors, saving the point(s) which give the largest projection vector.
  3. Now you have candidate points which could "touch" the opposite side. What remains is to find a slope for that line. A good starting slope is probably the one you drew which cuts the angle in half, just that you make it go through one of the points found in 2).
$\endgroup$

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.