TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Saturday, June 09, 2007

Fair Partitions - IV

After a longish gap, we continue on the conjecture:
"For every positive integer N, any convex polygon allows breaking into N convex pieces so that all pieces have the same area and same perimeter."

1. Proof for N=2 (easy, although full of English)
------------------------
*Any* point on the perimeter of the convex polygon P, there is another point Q (call this the 'opposite point to P1') so that the line P-Q (direction important) divides the polygon into two equal area convex pieces. the two pieces will in general have different perimeter.

Let us begin with a specific point P1 on the boundary - its opposite point is P2. say, the equal area piece to left of cut line P1-P2 has greater perimeter.

Now, we move P1 along the perimeter (clockwise, say, does not matter which way). the opposite point P2 also moves in the same direction around the perimeter. Obviously when P1 reaches the initial position of P2, P2 will be at the initial position of P1. and now, the half area piece to the *right* of P1-P2 has greater perimeter, the opposite to what we started with. In other words, the difference between the perimeters of the two equal area pieces has changed sign.

So, assuming the perimeters of the two pieces change continuously (obvious), we have some position in between when the two equal area pieces of the polygon also will have equal perimeter - when the difference between perimeters is zero. QED.
-----------
2. The following 'restrictive sequential' approach will not work in general for general N:

First cut a convex piece off *leaving behind a convex piece*. Then break a convex piece of same perimeter and area off the remaining piece, again leaving behind a convex piece. Repeat the process N-1 times.

eg: If a circular disc is to be broken into 3 pieces of equal area and perimeter (N=3), *if the first cut should leave behind a convex piece*, the first cut is necessarily a chord which breaks off 1/3 area of the disc. Now, it appears the remainder can be broken into two pieces with mutually equal area and perimeter *only* by making them congruent (identical) to each other. There is only one way of doing so and the resulting two pieces won't have the same perimeter as the piece broken first.
-------------
3a: A special case. N=3, the input polygon is a square. Here we arrive at a solution different from the obvious one of "two parallel cut lines". This approach led us to the claims set out in case 3b below.

We look at two extreme cases. (1) Consider two cut lines parallel to a *diagonal* of a square and equally spaced with respect to that diagonal (call this diagonal AB) and which cut the square into 3 equal area pieces. The middle piece is now a flat hexagon and the two *congruent* outer pieces are triangles. We note that the middle piece has more perimeter than the outer ones.

(2) Now choose an end point of the above diagonal, say A. Slide the end points of both cut lines which lie nearer to A, towards A. We simultaneously adjust the cut lines so that the two outer pieces and the middle piece continue to have equal area (and also keeping the outer pieces mutually identical so these two pieces continue to have equal perimeter). The ends of the cuts eventually meet at point A. Now, the merge the end points which have met and continue move them together along diagonal AB towards B. The middle piece now is a quadrilateral and the side pieces also have become quadrilaterals. Finally a configuration is reached when the middle piece is a *square* of side a/sqrt(3) and the side pieces are two mutually identical trapeziums. At this point, the middle piece has *less* perimeter.

Since we have changed the cuts continuously, the perimeters of the pieces must have changed continuously. And the perimeter of the middle piece, initially greater than the other two has changed to be less. So, in between, there is some position where the perimeter of the middle piece equalled that of the two side pieces.
----------------

3b. Thoughts on the N=3 case (this is tentative and might be knocked out by a counter; still am documenting our thoughts, for completeness). We present a chain of claims:

- From any point on the boundary of a convex polygon, we can draw two diverging lines which divide the polygon into 3 equal *area* pieces (obvious).

Consider a point P on the boundary of a convex polygon and the three equal area pieces generated by diverging lines starting at that point. We number the three pieces 1,2,3 in say, clockwise order as viewed from P.
Claim 1: we can always find at least one P on the boundary of the input polygon so that the 'outer' equal area pieces *1 and 3* will also have equal perimeter.

Note: there are convex polygons for which the middle piece 2 never has same perimeter as the others - for example a circle. And we *do not* look at diverging lines which yield same perimeter for pieces 1 and 2 and a different value for piece 3.

Claim1 is provable from continuity.

- Now, we stand at a point P so that two lines diverging into the polygon divide the polygon into three equal area pieces and pieces 1 and 3 have same perimeter. now, consider the two fan shaped regions formed by the two cuts (the interior of piece 2 and its opposite region in the exterior of the polygon).

Claim 2: we always have a curve (maybe even a line) passing thru P and extending into the two fan shaped regions meeting at P so that from every point on this curve, we can have a Y formed by three cut lines meeting inside the polygon (if the point is inside polygon) or a V (if outside) so that all pieces are convex and the pieces 1 and 3 continue to have equal perimeter - ie. a curve along which the perimeter of peces 1 and 3 vary equally from their value at P (and all continue to be convex and also have same area). We are not sure about claim 2 although it looks correct due to the convexity of the input polygon and the way we have chosen P.

Claim 3: The two values of the perimeters ({p(1) and p(3)} and {p(2)} vary continuously }on the curve described in claim 3, and there will always a point so that all the 3 perimeters are the same. That is all.

0 Comments:

Post a Comment

<< Home