TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Friday, July 27, 2007

Fair Partitions - V

Here is a bit more on the conjecture we had formulated a while ago:
"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."

The news is that it has been listed as an open problem (with rather different wording) at http://maven.smith.edu/~orourke/TOPP/P67.html#Problem.67

We have two more small findings (tentative) to report:
1. For any N, any convex polygon can be divided into N convex pieces all of equal perimeter (not looking at their areas) by a family of suitably spaced parallel lines of any orientation => there are infinitely many ways of cutting the convex polygon into N convex pieces of equal perimeter - just like there are infinitely many ways to cut it into N convex pieces of equal area. This appears to add strength to the conjecture.

2. We made the following proposition: Given two convex polygons P and Q of equal area and perimeter *which together form another convex polygon*. Let P be cut into P1 and P2 where the two pieces have equal area and perimeter and Q, similarly into Q1 and Q2. We can have some pair of partitionings which make P1, P2, Q1 and Q2 all of same area and perimeter.

If this proposition can be proved, the main conjecture can be proved for N = any power of 2.
However, it appears that the above proposition is not necessarily true, at least as far as we can make out. So, the conjecture retains its mystery.

------------------------------------------------------------------------------------
Apparent Failure of N=2 to *recursively* generalize to N = 2^N in a straightforward manner
------------------------------------------------------------------------------------
Example:
------------
- Polygon P1 is an isosceles triangle with a narrow base.
- Polygon P2 is a *trapezium* with same base length and one base angle equal to 90 degrees. P2 also has slightly less 'height' than the triangle P1; we can now adjust its other sides so that both P1 and P2 have same area and perimeter.

- Now, consider the large convex polygon P formed by joining P1 and P2 along their bases.

We find that P has exactly *3 bisections* so that the 2 resulting pieces have both equal area and perimeter (the obvious parition into P1 and P2 themselves plus 2 other partitions). In the specific numerical example we tried, *none of these 3 bisections* seems to give two pieces, which when bisected further gave 4 resultant convex pieces all with same area and perimeter - the final 4 pieces all have same area but their perimeters always come in 2 mutually different pairs.

A specific numerical case:

P1, the triangle has vertices: (0,0), (6, 20), ( 12, 0);
P2, the trapezium has vertices: (0,0), ( 12, 0), ( 12,
-18.992), ( 11.3631,-18.992);

For large polygon P, formed by joining P1 and P2 along (0,0) - (12,0), we find P can be cut into 2 convex pieces of equal area and perimeter in 3 different ways.

- by the the obvious line joining (0,0) and (12,0)
- the line joining (0.50602,1.68673) and (12, -1.76073).
- the line joining (2.50594,-4.18836) and (10.5974,4.67521).

We considered each of these 3 bisections of P and looked at further bisections of the 2 resulting pieces. Numerically, in none of these cases could we find 4 resultant pieces all of same area and perimeter.