Fair Partitions - III
This is the third part of the present trip of partitioning *convex* polygons into equal area pieces with additional constraints.
We (Ramana Rao and self) make an attempt to solve a specific case of the larger problem - to split a triangle into 3 convex pieces with equal area and perimeter.
After this attempt, I tend to believe: if we are to partition a convex polygon into convex pieces with equal area using the *least total length of cuts*, the resulting pieces need not all be of the same perimeter (just a guess). It is well-known that if all we need are equal area pieces with least total length of cuts, the pieces need not even be convex. So, one could also wonder if insisting on the pieces having same perimeter *and* same area and also that the total length of cuts is to be minimized, we are guaranteed convex pieces.
------------------
Cutting a triangle into 3 pieces of equal area and perimeter:
------------------
Here we try to deal mainly with long and thin triangles. For reasonably 'fat' ones - those with all three angles comparable, things could be easier - for an equilateral triangle, it is trivial.
Note: Of course, my feeling is that what follows works for ALL triangles! But, even for thin triangles, I am not sure if the approach is *not an overkill*!
--------
A simple specific example or the argument:
Dividing an equilateral triangle into 3 pieces with same area and perimeter.
Let one side of the input equilateral triangle T be the base and its opposite vertex, the apex.
1. The input equilateral triangle T is initially divided into three equal area pieces with apexes meeting at the apex of T and each having base = 1/3 of the input T. Obviously the two side pieces have greater perimeter than the middle piece.
2. Slide down the apexes of the side triangles until they both reach a height 2/3 of the altitude of T. Simultaneously, increase the base of both side pieces at the expense of the middle piece until the middle piece just has one point on the base of T. ie. the bases of both the two side pieces have increased by a factor of 3/2 from their initial value. Now, it is easy to see that the areas of the three pieces (the two side pieces which are now triangles and the middle piece which is a quadrilateral) are all equal. Crucially, the middle piece now has greater perimeter than the two side pieces.
3. Note that at the initial point in the sliding, the middle piece had less perimeter and at the end, the middle piece has more perimeter. So somewhere in the middle, the perimeters all have to necessarily equal since intuitively, at every intermediate stage of the sliding process, we can have equal areas for all the three pieces - a pentagon (the middle piece) and two triangles.
This approach has not given us the obvious way to divide an equilateral triangle into three congruent isosceles triangles (which meet at the centroid of the equilateral triangle) but gives an intro to the general argument below
-------
For a general triangle.
1. Identify the shortest side of the given triangle and make it the 'base' of the triangle. The angles at the end of the base will be called base angles; the vertex opposite to the base will be called 'apex'. Note: the base perhaps need not be the shortest side, but things appear clearer with such an assignment.
Divide the base into three equal portions. Connect the ends of the three portions to the opposite vertex with lines. Now, the triangle has been divided into three equal area triangular pieces - with different perimeters (in general).
2. Now among the three pieces, identify the piece with least perimeter. This will either be (case i) the middle piece (if the two base angles are both less than 90) or (case ii)one of the end pieces (if one base angle is obtuse).
We now try to reduce the perimeters of the other two pieces while keeping the areas of all 3 pieces constant. The above two cases are treated separately. Note: In both cases, the apexes of all the three equal area pieces *initially* coincide with the apex of the input triangle.
Case (i): We increase slightly the bases of the two side pieces (these have more perimeter). This base increase is at the expense of the middle piece. Now, to keep the areas of the side pieces constant, their altitudes would have to be reduced by a greater extent. This we do by sliding the apexes of these two side pieces down along the two sides (other than the base) of the input triangle - thus converting the middle piece into a pentagon. It is clear that the perimeters of the two side pieces reduce considerably whereas the middle piece which originally had least perimeter would slightly increase its perimeter - at any rate the perimeter of the middle piece does not decrease as fast as that of the side pieces. It looks, by this process, the perimeters of all three pieces can be equalized - the result will be a two triangles and a pentagon in the middle.
Case (ii): In this case, one end piece has the largest perimeter, the middle piece will have the second largest perimeter and the other end piece will have least perimeter. We could convert the end piece with the largest perimeter into a triangle with slightly larger base and a much reduced altittude and hence perimeter - the altitude reduction will be by sliding the apex of this piece down the longest side of the input triangle. The middle piece has now become a quadrilateral. We now increase the base of the middle piece (both base increases we have done are at the expense of the base of the end piece which originally had least perimeter) and slide its highest vertex down the longest side of the input triangle. Thus the middle piece, originally an obtuse triangle, turns into a shorter and fatter quadrilateral with same area - and less perimeter. The end piece with originally least perimeter now turns into a quadrilateral with slightly narrower base but with perimeter slightly increased. The resulting pieces in this case are two quadrilaterals and a triangle.
Thus, it appears that in both cases, we can reduce the perimeter of the pieces which have more perimeter, and get the perimeters of all three pieces to equalize. I hope this exhausts all possibilities.
Generalization(?)
-----------------
And assuming the above argument is correct and complete, it also indicates how to cut a triangle into *N* pieces all with equal area and perimeter. We put N-1 equally spaced points on the base and form N equal area triangular pieces by connecting these points with the apex. Now, the perimeters of the triangles, in a left to right order either
(1) begins with a high value, steadily decreases and again increases to another maximum - this is for both base angles are less than 90 or
(2)begins with the highest (or lowest) value and steadily reduces (or increases) to a minimum (or maximum) value - when one base angle is obtuse.
Both cases, which are essentially analogous to the case (i) and (ii) treated above, appear to admit similar solutions by similar sliding of vertices. Case (i) will lead to two triangles at the ends, a pentagon in the middle containing the apex, and the rest of the pieces are quadrilaterals. Case (ii) yields a triangle at an end and all other pieces will be quadrilaterals.
The above are only plausibility arguments, not conclusive proofs. More to understand; and of course, this whole line of thinking can be demolised by a single well-aimed 'counter-punch'!
Update (October 22, 2008):
--------------------------
Some experimental work was done on the above 'sliding vertices' proposal. We tried to fair partition *right triangles* into N pieces for various N. The output is not conclusive.
For example, an isosceles right triangle with base - 10 units and along +X axis and altitude - 10 units along +Y, we could find fair partitions for up to N=10. If the base and altitude are not equal, the larger of the two could be taken as the base and we could go on for larger values of N - upto 20 and even more depending on the ratio between the sides. But evidence points to: for arbitrarily large N, merely sliding the vertices along the hypotenuse and base (with no cutlines meeting in the interior of the input triangle) might not suffice. Further work is in progress.
A specific example: base 10, altitude 10. 8 pieces required.
X coordinates of the cutline ends on the hypotenuse: 0.000000 0.095000 0.284853 0.553162 0.898463 1.335723 1.884090 2.708066
X coordinates of the cutline ends on the base: 0.000000 1.166078 2.280096 3.384029 4.506422 5.671883 6.919630 8.285777
Details of the 8 resulting pieces:
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.207162 area: 6.250001
(the 8th piece has a slightly different perimeter. fine-tuning the position of the cutlines can achieve arbitrarily closer equality.)
We (Ramana Rao and self) make an attempt to solve a specific case of the larger problem - to split a triangle into 3 convex pieces with equal area and perimeter.
After this attempt, I tend to believe: if we are to partition a convex polygon into convex pieces with equal area using the *least total length of cuts*, the resulting pieces need not all be of the same perimeter (just a guess). It is well-known that if all we need are equal area pieces with least total length of cuts, the pieces need not even be convex. So, one could also wonder if insisting on the pieces having same perimeter *and* same area and also that the total length of cuts is to be minimized, we are guaranteed convex pieces.
------------------
Cutting a triangle into 3 pieces of equal area and perimeter:
------------------
Here we try to deal mainly with long and thin triangles. For reasonably 'fat' ones - those with all three angles comparable, things could be easier - for an equilateral triangle, it is trivial.
Note: Of course, my feeling is that what follows works for ALL triangles! But, even for thin triangles, I am not sure if the approach is *not an overkill*!
--------
A simple specific example or the argument:
Dividing an equilateral triangle into 3 pieces with same area and perimeter.
Let one side of the input equilateral triangle T be the base and its opposite vertex, the apex.
1. The input equilateral triangle T is initially divided into three equal area pieces with apexes meeting at the apex of T and each having base = 1/3 of the input T. Obviously the two side pieces have greater perimeter than the middle piece.
2. Slide down the apexes of the side triangles until they both reach a height 2/3 of the altitude of T. Simultaneously, increase the base of both side pieces at the expense of the middle piece until the middle piece just has one point on the base of T. ie. the bases of both the two side pieces have increased by a factor of 3/2 from their initial value. Now, it is easy to see that the areas of the three pieces (the two side pieces which are now triangles and the middle piece which is a quadrilateral) are all equal. Crucially, the middle piece now has greater perimeter than the two side pieces.
3. Note that at the initial point in the sliding, the middle piece had less perimeter and at the end, the middle piece has more perimeter. So somewhere in the middle, the perimeters all have to necessarily equal since intuitively, at every intermediate stage of the sliding process, we can have equal areas for all the three pieces - a pentagon (the middle piece) and two triangles.
This approach has not given us the obvious way to divide an equilateral triangle into three congruent isosceles triangles (which meet at the centroid of the equilateral triangle) but gives an intro to the general argument below
-------
For a general triangle.
1. Identify the shortest side of the given triangle and make it the 'base' of the triangle. The angles at the end of the base will be called base angles; the vertex opposite to the base will be called 'apex'. Note: the base perhaps need not be the shortest side, but things appear clearer with such an assignment.
Divide the base into three equal portions. Connect the ends of the three portions to the opposite vertex with lines. Now, the triangle has been divided into three equal area triangular pieces - with different perimeters (in general).
2. Now among the three pieces, identify the piece with least perimeter. This will either be (case i) the middle piece (if the two base angles are both less than 90) or (case ii)one of the end pieces (if one base angle is obtuse).
We now try to reduce the perimeters of the other two pieces while keeping the areas of all 3 pieces constant. The above two cases are treated separately. Note: In both cases, the apexes of all the three equal area pieces *initially* coincide with the apex of the input triangle.
Case (i): We increase slightly the bases of the two side pieces (these have more perimeter). This base increase is at the expense of the middle piece. Now, to keep the areas of the side pieces constant, their altitudes would have to be reduced by a greater extent. This we do by sliding the apexes of these two side pieces down along the two sides (other than the base) of the input triangle - thus converting the middle piece into a pentagon. It is clear that the perimeters of the two side pieces reduce considerably whereas the middle piece which originally had least perimeter would slightly increase its perimeter - at any rate the perimeter of the middle piece does not decrease as fast as that of the side pieces. It looks, by this process, the perimeters of all three pieces can be equalized - the result will be a two triangles and a pentagon in the middle.
Case (ii): In this case, one end piece has the largest perimeter, the middle piece will have the second largest perimeter and the other end piece will have least perimeter. We could convert the end piece with the largest perimeter into a triangle with slightly larger base and a much reduced altittude and hence perimeter - the altitude reduction will be by sliding the apex of this piece down the longest side of the input triangle. The middle piece has now become a quadrilateral. We now increase the base of the middle piece (both base increases we have done are at the expense of the base of the end piece which originally had least perimeter) and slide its highest vertex down the longest side of the input triangle. Thus the middle piece, originally an obtuse triangle, turns into a shorter and fatter quadrilateral with same area - and less perimeter. The end piece with originally least perimeter now turns into a quadrilateral with slightly narrower base but with perimeter slightly increased. The resulting pieces in this case are two quadrilaterals and a triangle.
Thus, it appears that in both cases, we can reduce the perimeter of the pieces which have more perimeter, and get the perimeters of all three pieces to equalize. I hope this exhausts all possibilities.
Generalization(?)
-----------------
And assuming the above argument is correct and complete, it also indicates how to cut a triangle into *N* pieces all with equal area and perimeter. We put N-1 equally spaced points on the base and form N equal area triangular pieces by connecting these points with the apex. Now, the perimeters of the triangles, in a left to right order either
(1) begins with a high value, steadily decreases and again increases to another maximum - this is for both base angles are less than 90 or
(2)begins with the highest (or lowest) value and steadily reduces (or increases) to a minimum (or maximum) value - when one base angle is obtuse.
Both cases, which are essentially analogous to the case (i) and (ii) treated above, appear to admit similar solutions by similar sliding of vertices. Case (i) will lead to two triangles at the ends, a pentagon in the middle containing the apex, and the rest of the pieces are quadrilaterals. Case (ii) yields a triangle at an end and all other pieces will be quadrilaterals.
The above are only plausibility arguments, not conclusive proofs. More to understand; and of course, this whole line of thinking can be demolised by a single well-aimed 'counter-punch'!
Update (October 22, 2008):
--------------------------
Some experimental work was done on the above 'sliding vertices' proposal. We tried to fair partition *right triangles* into N pieces for various N. The output is not conclusive.
For example, an isosceles right triangle with base - 10 units and along +X axis and altitude - 10 units along +Y, we could find fair partitions for up to N=10. If the base and altitude are not equal, the larger of the two could be taken as the base and we could go on for larger values of N - upto 20 and even more depending on the ratio between the sides. But evidence points to: for arbitrarily large N, merely sliding the vertices along the hypotenuse and base (with no cutlines meeting in the interior of the input triangle) might not suffice. Further work is in progress.
A specific example: base 10, altitude 10. 8 pieces required.
X coordinates of the cutline ends on the hypotenuse: 0.000000 0.095000 0.284853 0.553162 0.898463 1.335723 1.884090 2.708066
X coordinates of the cutline ends on the base: 0.000000 1.166078 2.280096 3.384029 4.506422 5.671883 6.919630 8.285777
Details of the 8 resulting pieces:
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.263170 area: 6.250000
perimeter: 21.207162 area: 6.250001
(the 8th piece has a slightly different perimeter. fine-tuning the position of the cutlines can achieve arbitrarily closer equality.)
posted by R.Nandakumar @ 11:11 PM
0 Comments:
Post a Comment
<< Home