Geometry Optimization – Smallest Triangle to Contain a Square

geometryoptimization

I was looking at this stack exchange question* and started thinking about the case of a polygon with 4 sides: a square.

The question asks for a program that can take a polygon of N sides and return the smallest possible polygon of N-1 sides that contains the original polygon.

Thinking about it, I wasn't sure what the optimal triangle encapsulating a square would look like. In KSab's answers, he returns a triangle that looks like this:

enter image description here

This area is 2*(area of the square). With some easy guess-and-check work I found that this seems to be optimized. How do you prove that there is no better solution?

EDIT: another consideration for the orientation of the triangle could be this:
enter image description here

Best Answer

If any vertex of the triangle coincides with any vertex of the square, then we very quickly find that the smallest such enclosing triangle must be a right triangle with two vertices of the square on each leg of the right triangle and one vertex of the square on the hypotenuse.

Consider the case where no vertex of the triangle coincides with any vertex of the triangle. Clearly, there must be at least one vertex of the square on each side of the triangle, for if there is a side with no vertex of the square on it, then we can draw a line parallel to that side through the vertex nearest to that side, and this line will "cut off" part of the original triangle, resulting in a smaller triangle.

Let the enclosing triangle be $\triangle ABC.$ Suppose that only three vertices of the square lie on sides of $\triangle ABC,$ and let $D$ be the vertex that does not lie on a side of $\triangle ABC.$ The following diagram is a general representation of this case:

general triangle touching only three vertices of the square

Now consider the alternative enclosing triangles $\triangle AB'C'$ and $\triangle A''B''C,$ each of which has one side collinear with $AC$ and another side collinear with a side of the square. We have similar triangles $\triangle A''GF$ and $\triangle FEC',$ and of course $|EF| = |FG|,$ so $|A''G|\cdot|EC'| = |EF|^2.$ Therefore $|A''G|$ and $|EC'|$ cannot both be larger than $|EF|.$ We therefore pick a side that is not larger than $|EF|$; without loss of generality, suppose that side is $|EC'|,$ that is, $|EC'| < |B'E|.$ Since $\angle BED \cong \angle CEC'$ and $|EC| < |EB|,$ $\triangle CEC'$ fits entirely inside $\triangle BEB'.$ That is, when we replace $\triangle ABC$ by $\triangle AB'C',$ we add a smaller region than we remove, and hence $|\triangle AB'C'| < |\triangle ABC|.$ We conclude that all vertices of the square must lie on sides of the smallest enclosing triangle, which implies that at least two of them must lie on the same side of that triangle.

Now label any such enclosing triangle $\triangle ABC$ so that two vertices of the square lie on $BC.$ Moreover, suppose that the altitude of the triangle from $A$ is greater than twice the side of the square. This condition is illustrated in the following diagram:

one side of the square lies on BC, altitude from A is > 2 times side of square

Now consider the triangle $\triangle A'B'C$ where $A'$ lies on $AC$ and the distance from $A'$ to $BC$ is exactly twice the side of the square. Then $\triangle BDB' \cong \triangle EDA',$ so in replacing $\triangle ABC$ with $\triangle A'B'C$ the area we remove ($\triangle ADA'$) is greater than the area we add. We conclude that if $\triangle ABC$ is the smallest enclosing triangle and two vertices of the square lie on $BC,$ then the altitude from $A$ is no greater than twice the side of the square.

But suppose that the altitude from $A$ is less than twice the side of the square, as illustrated in the following diagram:

enter image description here

Consider the triangle $\triangle A'B'C$ where $A'C$ is collinear with $AC$ and the distance from $A'$ to $BC$ is exactly twice the side of the square. Then $\triangle BDB' \cong \triangle EDA',$ and so if we replace $\triangle ABC$ with $\triangle A'B'C$ the area we add ($\triangle ADA'$) is less than the area we remove. We conclude that if $\triangle ABC$ is the smallest enclosing triangle and two vertices of the square lie on $BC,$ then the altitude from $A$ is no less than twice the side of the square.

But since we already know the altitude from $A$ is no greater than twice the side of the square, we must conclude that the altitude from $A$ is exactly twice the side of the square. This condition is illustrated in the following diagram:

enter image description here

We consider another triangle, $\triangle AB'C',$ where $B'C'$ is collinear with $BC$ and again the altitude from $A'$ is exactly twice the side of the square. For either of these triangles, the side $BC$ or $B'C'$ is parallel to the opposite side of the square and is exactly twice as far from $A$ or $A'$; therefore $|BC| = |B'C'| = 2s$ where $s$ is the side of the square. Each triangle has a height of $2s$ relative to this base, so the area of either triangle is $2s^2.$

There is therefore no unique smallest enclosing triangle. Any enclosing triangle such that two vertices of the square lie on one side of the triangle, the other two vertices lie on the other two sides, and the altitude from the opposite vertex of the triangle is twice the side of the square (or, equivalently, the first-mentioned side is twice as long as a side of the square) will have the minimum area. The triangle could be an isoceles right triangle, or an isoceles triangle in which exactly one side is twice the side of the square (and is collinear with one side of the square), or any of a great number of scalene triangles that fit the last condition; but in no case can you make an enclosing triangle smaller than a right triangle whose right-angled vertex coincides with a vertex of the square. The minimum area of an enclosing triangle is twice the area of the square.