TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Saturday, August 22, 2020

Oriented Convex Containers - Further Questions

This post attempts to go further from the following two arxiv documents:

https://arxiv.org/abs/1802.10447 [1]
https://arxiv.org/abs/2005.10245 [2]

The isosceles triangle and the right triangle are among oriented convex regions (as defined in [1]). We discussed questions of optimal oriented containers of convex regions in [2] - the containers considered/mentioned in [2] are the semicircle, circular segment, circular sector in ([2]).

The problem of finding the smallest area isosceles triangle that contains a given triangle (not a general convex polygon C) has been settled in (https://arxiv.org/pdf/2001.09525.pdf ). The smallest perimeter isosceles container of a given triangle is, to our knowledge, still open.

Here, we collect 8 algorithmic questions that come in 2 broad categories.

Given a convex region R, find:
1. the isosceles triangle of smallest area that contains R.
2. the isosceles triangle of smallest perimeter that contains R
3. the right triangle of smallest area that contains R.
4. the right triangle of smallest perimeter that contains R.
and
5. the isosceles triangle of largest area that is inscribed in R
6. the isosceles triangle of largest perimeter that is inscribed in R.
7. the right triangle of largest area that is inscribed in R
8. the right triangle of largest perimeter that is inscribed in R.

Lemma 1: The smallest area isosceles triangle T that contains any given convex polygonal region R is such that at least an edge of R lies entirely on an edge of T.
Note: There appears to be only one exception to this lemma - when 3 vertices of R are such that one coincides with the mid point of the base of T and the other two, lying on the arms of T are symmetrically placed with respect to the bisector of the apex at exactly a suitable height.

Proof: We try to prove the lemma by contradiction. Assume that each edge of the desired triangle T only passes through a vertex of R (Obviously, all sides of the smallest required triangle has to at least touch R). In pictures below those three vertices of R are shown as black dots ( the rest of R is not shown). We examine 2 cases.

Case 1:


If perpendiculars drawn to edges of T from two of the vertices of R that lie on T intersect inside T at a point C as shown above, we draw the line from C to the third vertex r. Now, If we rotate the plane as a whole with C as center and keeping the triangle T fixed the 2 vertices p and q will move into the interior of T for both CW and CCW rotations and vertex r will also move into the interior for at least one of the rotation directions (here it is CCW). So, we can get the whole of R into the interior of the triangle and so the triangle is necessarily suboptimal as a least area container of R.

Case 2:


If perpendiculars drawn to the triangle T at 2 of the 3 vertices of R that lie on T (p and q) meet outside T at C, we have an entire half line (shown by the red arrow) such that if we rotate the plane about any of point on the half line, there is one rotation direction (here CCW) for which p and q will necesarily move into the interior of T. Now, draw a perpendicular to T from the other vertex r and make it cut the red half line at D. Any point within the segment CD can be the center of a CCW rotation such that R can be moved entirely inside T. So, T is again suboptimal.

Note 1: If instead of q, we have q' as one of the vertices of R lying on T, then, for any point on segment DE as center and CW as rotation sense we can move R entirely into interior of T.

Note 2: Let us also note that in above arguments there is nothing specific to area or isosceles containers. So, we conclude: the least area/ least perimeter triangle T with isosceles/right triangle propery that contains a given convex polygonal region R is such that an edge of R lies entirely on an edge of T - again with the exception mentioned above.

Note 3: The above lemma could give us a starting point for an algorithm that can find such triangle containers.

Let me conclude with a guess:
Guess: It appears that the maximum area/perimeter isosceles triangle inscribed in a given convex polygonal region R has at least 2 vertices coincident with vertices of R. There are only experimwntal indications...No proof idea.

And no idea about inscribed right triangles!

0 Comments:

Post a Comment

<< Home