Among the issues mentioned there, the least area and least perimeter isosceles triangles that contain a given convex region is, as far as I know, yet to be fully resolved.
In that article, I had not touched upon the issue of finding and characterizing the smallest general triangle that just contains an input convex region. Here, 'smallest' could mean least area or least perimeter. As I found out recently, there are papers by Klee and Laskowski and by O'Rourke et al that date from 1980s which study and solve the question of least area triangle container of a given convex polygon.
However, finding the least perimeter triangle containing a given convex region is probably not yet done (to my knowledge). Here are some preliminary thoughts on this question. Note: I shall update or correct with proper date stamps (or if need arises, junk) this post as I learn more.
As given in the paper by O'Rourke and others mentioned above, the two key properties that characterize the least area triangle container (call this T) of a given convex polygonal region R are:
1. The mid point of each side of T is on R
2. At least one side of T is flush with R (ie is a side of T is a superset of a side of R).
There may be many triangles that has these properties vis-a-vis R and each is a local minimum in area of containers. One of these is the global minimum.
----------
Note inserted on October 10th 2018:
The problem of min perimeter triangle container is indeed well studied as I just learned. The first bit of major progress was made by DePano back in 1987. He proves the following basic lemma: The least perimeter containing triangle of a convex region R has at least one side flush with R. Using this lemma, efficient algorithms to find the container too were established. So most of this post are only notes to myself except perhaps, the last bit below named: "Further Questions"
----------
Consider the following figure:
ABC is a right triangle. M1, M2 and M3 are midpoints of its sides. Then a convex region (drawn in thicker lines; call this region R ) is shown inscribed in ABC with the following properties.
- An edge of R is flush with the base of ABC and contains the mid point of the base. Another edge of R is flush with the altitude of ABC and contains its mid point.
- Another edge of R, PQ is flush with the hypotenuse of ABC and contains the mid point M2 of the hypotenuse as shown. Above Q (going CCW), the boundary of R deviates inwards from the boundary of ABC.
Now, from what one understands from the above mentioned results, ABC is the least area triangular container of C.
Consider another right triangle AB'C': this has slightly less altitude than ABC and slightly more base and its hypotenuse only touches R at the end point Q of the edge of R that is flush with ABC. Obviously, AB'C' is another triangle that contains C.
Now, if ABC is chosen to have narrow base, it is seen experimentally that the newly constructed right triangle AB'C' has less perimeter and more area than ABC. So we conclude that the least perimeter triangle that contains a given convex region is not in general the same as the least area triangle container
Note: We don't say AB'C' is the least perimeter triangle container of R. We only note it is better than ABC.
------------
Now, we ask whether the least perimeter containing triangle has the above properties of the least area containing one. Consider this slightly changed figure shown below:
In this, ABC is unaltered and R has been infinitesimally changed from figure 1 so that it only touches the base and altitude of ABC at the mid points of these sides of ABC. PQ has been retained as a straight edge of R and is flush with the hypotenuse of ABC as before. Now, it looks conceivable that ABC remains the least area containing triangle of the altered R; even if there is another containing triangle with slightly less area than ABC, it appears to have more perimeter (ie is longer and thinner) than ABC. So, the same AB'C' is a lower perimeter triangular container or R than the least area container.
So, we guess that the min perimeter triangular container
- need not have mid points of its sides on the contained polygon
- need not have any side of it flush with the contained polygon.
-------
Further questions:
Which shape of R is such that its least area containing triangle and least perimeter containing triangle have greatest difference in their areas and perimeters?
More precisely, there are two questions:
- which shape of R maximizes the ratio between the area of its least perimeter triangle container and the area of its least area triangle container?
- Which shape of R maximizes the ratio between the perimeter of its least area triangle container and the perimeter of its least perimeter triangle container?
I am not quite sure if the answer to both these questions is the same shape.
The question of least perimeter quadrilateral containing R too seems not studied; the quad of least perimeter containing R may well be different from the quad of least area that contains R.
----------------------
No comments:
Post a Comment