TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, September 12, 2019

Partitioning into Isosceles Triangles


Basic Question: To partition a given polygon (not necessarily convex) with N sides into the least number of isosceles triangles.

All polygons do admit such a partition. And some N-gons might need at least 4(N-2) isosceles triangles.
Indeed, every N-gon has a triangulation into N-2 triangles. Any triangle can be cut into two right triangles and further, any right triangle admits a partition into 2 isosceles triangles (for this, simply join its circumcenter that lies on the hypotenuse to the opposite vertex). So, we have an obvious upper bound of 4(N-2) for the number of isosceles triangles that result from partitioning any given N-gon. And this bound appears tight. For, there are polygons like this:

where any triangulation appears to yield only obtuse triangles. A general obtuse triangle appears NOT to allow partition into less than 4 isosceles triangles.

Further question: What if a given N-gon is to be cut into the least number of acute isosceles triangles?

Here is a discussion on how few acute (not necessarily isosceles) triangles can result when an obtuse triangle is partitioned. An argument is given that says at least 7 acute triangle pieces may result from a single obtuse one.

So to cut any given N-gon into acute isosceles triangles, one can

1. triangulate the N-gon into ~ N triangles.
2. Divide each triangle into 2 right triangles (yielding a total of 2N right triangles) and then partition each right triangle into 2 isosceles triangles - note that except when the right triangle is itself isosceles, one of these 2 isosceles triangles is acute and the other is obtuse. So, at the end of this step, we have 2N acute isosceles triangles and 2N obtuse isosceles triangles.
3. Now, partition each of the 2N obtuse isosceles triangles into 7 acute pieces as described in the above linked page. By the symmetry of the input obtuse isosceles triangle, it is seen that each of the 7 acute triangles is also isosceles. Thus we have a total of 2N + 7 X 2N = ~16 N acute isosceles triangles.

Remaining Question: Is 16N a tight lower bound on the least number of acute isosceles pieces that can team up to recreate any given N-gon?

0 Comments:

Post a Comment

<< Home