TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Saturday, November 24, 2007

Fair Partitions - VII

This is a status report on the fair partitioning business.

First, a bit of speculation. We have been trying to prove the convex fair partitioning conjecture ("given any integer N, any convex polygon allows paritioning into N convex pieces all of equal area and perimeter") for N=3 - ie. fair partitioning into 3 convex pieces.

In an earlier post, some continuity-based speculations had been floated. Now we think the following could work:

- There is a *large region* in the plane of the convex polygon (this large region includes a portion of the interior of the plane and also *most* of its exterior), the points P of which satisfy: (1) the polygon can be cut into 3 convex pieces of equal area by 3 rays diverging from P with (2) the extra requirement that one of these rays goes in the +X direction.

- Call the three resulting equal area convex pieces 1, 2 and 3, measured counterclockwise from the +X direction and their perimeters, P1, P2 and P3.

- There will be a continuous region in the plane so that for points there (as the sources of the rays) P1 is the greatest (ie. piece 1 has most perimeter), a region where P2 is greatest and likewise for P3. We could label these regions by P1, P2 and P3.

- We *guess* that from the P1 region we could go continuously either to the P2 region or to the P3 region; likewise from the P2 region we could cross over continously to P1 or P3 region and likewise for P3 region. This guess implies, there are dividing curves between the regions where P1=P2, P2=P3 and P3=P1 *and also* that these curves are bound to intersect. An intersection point between two of the curves is a meeting point from where 3 diverging rays, with one ray in +X do a convex fair partitioning of the given polygon.

Note 1: The angles between the rays need not all be less than 180 degrees. The pieces of the convex polygon that result should all be convex. That is all. Moreover, the ray in +X direction from the meeting point need not touch the polygon.

Note 2: Three such regions where each of P1, P2 and P3 are maximum, are expected to be present at least for one orientation of the polygon with respect to the X axis. That is sufficient for at least one meeting point for the rays and a partitioning of the type we need.

------------------
Now, we try to explicitly do some special cases of convex fair partitioning.

A. A regular hexagon into 7 pieces all of equal area and perimeter.

Consider the 'extreme configurations':

1. config 1: Hexagon of side 1, kept with a vertex, call this vertex 1 at the bottom and another - this is vertex 4 - at the top. A square (the area of this square has to be 3/7 of the hexagons) kept as a diamond inside the hexagon so that the centers of both coincide and a diagonal coinciding with diagonal 1-4 of the hexagon. The square can be divided into 3 identical rectangles and the rest of the hexagon into 4 identical pentagons.

In above state, the perimeter of each of the 3 rectangles constituting the central square is 2.81388. The perimeter of the 4 pentagons is 2.92894.

(the calculation uses the formula area of full hexagon = 6*sqrt(3)/4. and area of square is 3/7 of this and some basic trigonometry).

2. The other extreme config (config 2)is: Big regular hexagon unchanged. The square in the middle (appearing as a diamond) is gradually stretched vertically into a rhombus (of course, keeping its area constant)with the longer diagonal eventually coinciding with diagonal 1-4 of the regular hexagon.

The rhombus has the same area as the square of config 1 from which it is deformed. and the rhombus can be cut into 3 mutually identical parallelograms. the rest of the hexagon outside the rhombus can be obviously cut into 4 mutually identical quadrilaterals.

In this state, the perimeter of each of the 3 parallelograms which form the inner rhombus is 3.05208. the perimeter of each of the 4 outer pieces is now 2.95382.

Conclusion: config 2 can be reached by continuously deforming config 1. Throughout the deformation, the inner rhombus gives 3 identical parallelograms and the rest of the hexagon is formed of 4 identical pieces. In config 1, the 3 inner pieces have *lower* perimeter than the 4 outer pieces. In config 2, the 3 inner pieces have *greater* perimeter than the outer pieces. So, by continuity, there is a intermediate state where the perimeters of the two sets of pieces are equal. That settles the regular hexagon into 7 pieces case. If N = 5, the above continuity argument will still work with the square deformed into a rhombus as before but with area 1/5 of the big regular hexagon.

B. An equilateral triangle into 5 convex pieces:

Consider an equilateral triangle of side 5 units.We begin by dividing a side of the base AB of the triangle (any side can be the base) into 5 equal parts and connecting the dividing points to the opposite vertex, the apex C. Now, if we number the 5 pieces left to right as 1,2,3,4,5, extreme pieces 1 and 5 have max perimeter and the central piece 3 has least. All pieces have the same area.

Consider pieces 1 and 2 together as a single large triangular piece. We find that we can divide this piece into two pieces 1' and 2' of equal area and also equal perimeter by a line from a point on its side (segment AC) at a distance 0.4098 from the apex C to a point on the base at a distance 1.0892 from vertex A (basically, original piece 1 has had its base increased from 1 unit and height reduced keeping area constant but so that its perimeter reduces a bit).

Now, surprisingly, the perimeters of 1' and 2' are found to be exactly equal to that of central piece 3 which has not been touched. The areas of all pieces 1',2' and 3 are anyway equal. The same strategy employed to pieces 4 and 5 together finishes the partitioning.