TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Friday, August 24, 2007

Fair Partitions - VI

We countinue 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."

------
We recall the Definitions: Fair partition is a partition of a polygon which leaves all pieces with equal area and perimeter. A convex fair partition is a fair partition where all pieces are also convex.

We wondered if among all fair partitions possible for a convex polygon, the one with the least total perimeter of pieces - or least length of cuts - is a convex fair partition. But this appears to be *NOT* the case, at least for small N.

eg: Consider an isoscles triangle with base 1 and altitude 2 (the equal sides are then sqrt 5 each). Join a square of side 1 to the base to form pentagon. The area of this pentagon is 2 units. Take N = 2. ie we need to break the pentagon into 2 pieces of equal area and perimeter.

By inspection, the *only* convex fair partition is by the bisector of the apex of the isosceles triangle. And the length of the cut is 3 units. Now, it is possible to have another fair partitioning of the pentagon into one convex and one non convex pieces with cut length just around 1.7 units - considerably less than 3. So, the convex fair partitioning is not the 'best'.

The reason for considering the above line of thought was this: if somehow one can prove that for any non convex fair partitioning, there is always a better fair partitioning (better means one with less total of cut lengths) that can be achieved by tweaking one of the non convex pieces (and the remaining portion of the input polygon), we could have argued: "There definitely has to be *some* fair partitioning that has the least total of cut lengths. If any non convex fair partitioning can be improved, the fair partitioning with least cut lengths has to be one with no non convex pieces. This establishes the existence a convex fair partition thus proving the original conjecture".

But things do not appear to be so simple!

0 Comments:

Post a Comment

<< Home