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.)

'Fair Partitions' - II

Here we propose a proof for a weaker version of the claim floated in the last post here: Any convex polygon, for any N, can be partitioned into N equal area and equal perimeter pieces, *if the pieces need not be convex*.

-----------------
Proof for possibility of partitioning a convex polygon into N equal area and perimeter pieces which need not themselves be convex:
-----------------
1. We first divide the input polygon into N equal area pieces so that exactly 1 'inner' piece *does not* touch the boundary and each of the remaining N -1 pieces share some *finite* boundary with this inner piece (and also divide up the outer boundary of the input polygon among them). We argue how this can always be done a little later.

2. Now, we could deform the common boundary of the inner piece with each of its N-1 neighbors to make all N-1 neighbors have the same perimeter.

If two pieces share an edge, if we introduce some zigzags (with concavities) on that edge, the perimeter of both pieces increase by the same amount - and we can do this without changing their areas. So we note among the N-1 outer pieces, which has the highest perimeter and increase the perimeters of each of the other N-2 outer pieces to this value - by tweaking the common boundary of each of them with the inner piece.

3. Now, all outer pieces have same area and same perimeter. The inner piece also has the same area but a possibly very large perimeter since its boundaries with all outer pieces (except one) have been deformed. We now try to increase the perimeter of all outer pieces to equal this large value.

We note the difference between the perimeter of the inner piece and that of an outer piece - call this quantity d. Then we deform *all* the boundaries between the outer pieces - ie the dividing boundary between outer piece 1 and 2, then the boundary between 2 and 3 and so on - so that the increase in perimeter to both the pieces separated by a given boundary is d/2. So, when all boundaries have been deformed, every outer piece increases its perimeter by d - their areas should be kept constant - which is as desired.

Exception: If after step 2, the inner piece still has *less perimeter* than the common value of the perimeters of the outer pieces, we could tweak the boundary of the input piece with each of the outer ones equally so that every outer piece gains a little perimeter and the innter piece gains N-1 times that much so we could again equalize the perimeters.

A bit remains: how to divide the input convex polygon into N equal area pieces so that one piece is in the middle and the remaining N-1 surround it? For this, we could scale the input polygon by a factor of N and the resulting small polygon can be put somewhere inside the input polygon (this scaling will work if the input polygon is convex). This is the central piece. Then we can walk around the central piece and sweep out N-1 equal area pieces from the remaining 'annular' portion of the input polygon. These N-1 outer pieces are free to be be concave so we could force each of these to share a finite boundary with the inner piece.

Remarks:
-------

Obviously, this approach can cause all the pieces to have very large perimeters and they will also have jagged boundaries. No attempt has been made to minimize the sum of the perimeters of the pieces, which remains to be understood.

We can't see how this argument can be modified to handle the case where the pieces have also to be convex. But this argument does appear to allow us to prove this: "for any N, any (non-convex) polygon can be broken into (non-convex) N pieces all of equal area and perimeter" - the only new idea is to put an thinned down - almost insetted - polygon of area 1/N of the target polygon in the interior of the target (the thinned polygon will be of the same basic skeletal shape as the target and much thinner and will run along the entire length of the target; intuitively, such a polygon can always be found with the required area) - This skeletal polygon will serve as the central polygon in the above proof. The rest of the proof should go thru unchanged. Of course, now we have the question: how to partition a general polygon into general pieces of equal area and equal perimeter *minimizing the perimeter of each*?

---------
For the case when the pieces also have to be convex (the full version of the claim), we tried to find counter-examples like 'dividing a triangle into 5 convex pieces with equal area and perimeter' - no progress yet on that front.