2
$\begingroup$

Given acute triangle $ABC$ such that $AB$ is the longest side. I need to prove that the rectangle $PQRS$ of minimum area covering the whole of triangle $ABC$ has one side (say $PQ$) coincident with $AB$ and the opposite side $RS$ parallel to $PQ$ and passing through $C$.

(The application I have that needs this proof does not guarantee that $ABC$ is an acute triangle, only that point $C$ lies inside the strip defined by the two perpendiculars to $AB$ passing through points $A$ and $B$. But if angle $C$ is obtuse, it is much easier to prove that the minimal bounding rectangle is as stated.)

If the statement is untrue, I'd like to know the conditions for it to be wrong.

This is not as trivial (for a generic acute triangle) as it looks. I can show that the minimal bounding rectangle contains $A$, $B$ and $C$ on its boundary, since otherwise you could "slide" a side of the purported minimal rectangle inward until it does touch one of the vertices of the triangle and get a smaller bounding rectangle. I believe that the last such "sliding" step also shows that one of the vertices on the triangle must coincide with a vertex of the minimal bounding rectangle.

That is how far I have gotten in the forward direction. Working backwards, I think if one shows that one side of the minimal bounding rectangle coincides with a side of the triangle, it will not be hard to show that it would have to be the longest side.

Help would be appreciated.

$\endgroup$
  • $\begingroup$ If $ABC$ is acute, then a rectangle with one side coincident with any side of $ABC$ and whose opposite parallel side intersects the third point will have an area twice of that the triangle. The coincident side need not be the longest side of $ABC$. Nonetheless, I think having one side coincident is a necessary condition for an area-minimizing rectangle. $\endgroup$ – Joey Zou Aug 2 '16 at 22:49
  • $\begingroup$ There is a solution by taking barycentrical coordinates of the 4 vertices of the general rectangle with respect to the triangle (considered as fixed). The advantage of barycentrical coordinates is that areas are always easy to express through $3 \times 3$ determinants. Then, once the equations are obtained, it suffices to convert barycentrical coordinates into their "cousin" coordinates, that are "areal coordinates". I have not time enough this evening (already 1:12 CET). I will do it tomorrow. $\endgroup$ – Jean Marie Aug 2 '16 at 23:15
3
$\begingroup$

Note that in the case of an acute triangle you can align any side of the triangle with a side of the rectangle, and obtain the same minimal rectangle area, namely twice the area of the triangle.

I'm referring to the following figure:

enter image description here

We turn a circumscribing rectangle clockwise around the triangle so that when $\phi=0$ a side of the rectangle coincides with the side $AB$ of the triangle. The area $F$ of the rectangle then computes to $$F=bc\cos\phi\cos\theta={bc\over2}\bigl(\cos(\phi+\theta)+\cos(\phi-\theta)\bigr)={bc\over2}\bigl(\sin\alpha+\cos(\phi-\theta)\bigr)\ .$$ This is obviously smallest if $|\phi-\theta|$ is largest, namely $={\displaystyle{\pi\over2}}-\alpha$. In this way we obtain $$F_{\min}=bc\sin\alpha=2{\rm area}(\triangle)\ ,$$ as claimed.

$\endgroup$
  • $\begingroup$ Nice solution. I wondered if this solution could be explicited in terms of "classical" functions in shape analysis that are the support function (of a convex set) and its derived diameter function as recalled in page 3 of this article $\endgroup$ – Jean Marie Aug 4 '16 at 8:21
2
$\begingroup$

As you mentioned, an area minimizing rectangle must contain the vertices $A$, $B$, and $C$ on its boundary, and furthermore one of the vertices must coincide with one of the rectangle's vertices (otherwise there is a portion of the rectangle that we can "cut off").

Suppose $PQRS$ contains $ABC$, with $P$ coincident with $A$. Suppose none of the sides of $ABC$ intersected any of the sides of $PQRS$ outside of vertices. Then $B$ and $C$ cannot be on the edges of the rectangle containing $P$, so they are on $QR$ and $RS$, and they do not coincide with the other vertices of the rectangle. WLOG $B$ lies on $QR$ and $C$ lies on $RS$. To show that such a rectangle cannot be area minimizing, it suffices to show that the area of triangle $ABC$ is strictly less than half of that of $PQRS$. Let $l = PQ = RS$ and $w = PS = QR$, so that the area of $PQRS$ is $lw$. Let $l' = CS$ and $w' = BQ$, so that $l-l' = CR$ and $w - w' = BR$. Then the area of the rectangle outside of the triangle is the sum of the areas of the triangles $PQB$, $BRC$, and $CSP$, which are $\frac{1}{2}PQ*QB = \frac{1}{2}lw'$, $\frac{1}{2}BR*RC = (w-w')(l-l')$, and $\frac{1}{2}CS*SP = \frac{1}{2}l'w$, respectively. Hence, \begin{align} \text{Area}(ABC) &= \text{Area}(PQRS) - \text{Area}(PQB) - \text{Area}(BRC)-\text{Area}(CSP) \\ &= lw - \frac{1}{2}lw' - \frac{1}{2}(l-l')(w-w') - \frac{1}{2}l'w \\ &=\frac{1}{2}(2lw - lw' - (lw -lw' -l'w +l'w')-lw')\\ &=\frac{1}{2}(lw -l'w')\\ &<\frac{1}{2}lw = \frac{1}{2}\text{Area}(PQRS) \end{align} Here, the fact that $B$ and $C$ do not coincide with the vertices of the rectangle implies that both $w'$ and $l'$ are positive. Hence, if none of the sides intersected outside vertices, then the rectangle does not minimize area. It follows that an area minimizing rectangle must have an edge coinciding with an edge of the triangle, and furthermore the two edges must be exactly coincident, since otherwise we can again "cut off" extraneous parts of the rectangle.

$\endgroup$
2
$\begingroup$

@Joey Zou @G Cab

A web search using the fruitful keyword "bounding box" brought me to the following proven - and more general - result (ref [1]... 40 years ago):

"A rectangle with smallest area enclosing a polygon has a side colinear with one of the edges of its convex hull"

From there, it is almost immediate that, among the 3 sides, taking the longest one $AB$ ensures that one has a smallest area rectangle by taking the opposite side as passing through the third point $C$.

In this way, as the foot of the altitude issued from the opposite vertex $C$ is inside line segment $[AB]$, an immediate consequence is that the area of the rectangle is twice the area of the triangle.

As remarked by Joey Zou, if the triangle is acutangle (all angles $\leq \pi/2$), then any of its sides (not necessarily the longest one) is good for that : in each case, the area of the rectangle is twice the area of the triangle (see for example the case of a right triangle) ; thus we shouldn't speak about "the" but "a", smallest area-minimizing rectangle.

See as well [2], [3] and [4] for application to cartography.

[1] Freeman, H. and Shapira, R., "Determining the minimum-area enclosing rectangle for an arbitrary closed curve", Communications of the ACM 18: 409–413, 1975.

[2] https://en.wikipedia.org/wiki/Minimum_bounding_box_algorithms

[3] https://geidav.wordpress.com/tag/convex-hull/

[4] https://gis.stackexchange.com/questions/22895/how-to-find-the-minimum-area-rectangle-for-given-points

$\endgroup$
  • $\begingroup$ thanks for the hints to the more general case of polygons and closed curves. Remaining within the triangle, I cannot understand why such a very simple stuff is causing so much debate. Is the vectorial picture I gave (+ further comments) not enough to close the subject? $\endgroup$ – G Cab Aug 4 '16 at 0:08
  • $\begingroup$ @G Cab First, I think it is not correct that your answer has been downvoted : you have realy bringed something, but the objection has been well formulated by @David K : you show that 3 solutions in general are possible by using affine transforms (transvections) that "make an acute angle into a right angle" with preservation of area doubling because ratios of areas are affine invariants, but how can we prove that there is no way to have a rectangular bounding box with an area less than twice the area of the triangle ? $\endgroup$ – Jean Marie Aug 4 '16 at 8:10
  • $\begingroup$ @JeanMarie There is a quotable link for [1] here. The paper itself is behind a paywall, but the relevant result is stated in the freely available abstract. $\endgroup$ – dxiv Jan 12 '18 at 5:22
  • $\begingroup$ @dxiv Thanks. We have thus more information. $\endgroup$ – Jean Marie Jan 12 '18 at 5:34
0
$\begingroup$

Consider the vectors corresponding to the three sides $ \mathop {AB}\limits^ \to ,\mathop {\;AC}\limits^ \to ,\;\mathop {\;BC}\limits^ \to = \mathop {\;AC}\limits^ \to - \mathop {\;AB}\limits^ \to $ .
The area of the parallelograms constructed on any couple of sides will be the same $$ Area = \left| {\mathop {AB}\limits^ \to \; \times \mathop {AC}\limits^ \to } \right| = \left| {\mathop {AB}\limits^ \to \; \times \mathop {BC}\limits^ \to } \right| = \left| {\mathop {AC}\limits^ \to \; \times \mathop {BC}\limits^ \to } \right|$$ and you can always transform at least one of the parallelograms into a rectangle covering the triangle.

$\endgroup$
  • $\begingroup$ I dont understand well your last sentence. $\endgroup$ – Jean Marie Aug 2 '16 at 23:44
  • $\begingroup$ @JeanMarie In a triangle, two angles at least shall be acute, and they will individuate a side connecting them. A parallelogram including that side can then be "straightened" into a rectangle of same area by sliding the opposite side. The angles of 90° will cover the two acute ones and the whole rectangle will cover the triangle. $\endgroup$ – G Cab Aug 3 '16 at 0:16
  • $\begingroup$ This shows that you can equally well choose any side of the triangle to be one side of the rectangle, that is, the covering rectangle described in the question cannot be a unique minimum-area covering rectangle. But it is still a (non-unique) minimum-area covering rectangle, which this answer does not show. $\endgroup$ – David K Aug 3 '16 at 14:07
  • $\begingroup$ @DavidK , sorry I don't get exactly your comment. If the triangle is acutangle than any side can be the base of "a" covering rectangle, whose area is minimal, and equal twice that of the triangle. If instead one angle in the triangle is obtuse, then you have only one minimal rectangle, the one based on the largest (= adjacent to acute angles) side. I think all this is well clear from my answer. $\endgroup$ – G Cab Aug 3 '16 at 23:53
  • $\begingroup$ My answer has been downvoted: it would be instructive - besides POLITE - that who did it would also drop some motivation. Thanks $\endgroup$ – G Cab Aug 3 '16 at 23: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.