TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, September 28, 2006

'Fair' Partitions

Let us (N. Ramana Rao and self) float yet another geometric conjecture

****
Given any convex shape and any positive integer N. There exist some way(s) of partitioning this shape into N convex pieces so that all pieces have equal area and equal perimeter.
****

Note: We could define the 'fair partition' of a polygon as a partition into pieces of equal area and perimeter and further, a 'convex fair partition' as a fair partition in which the pieces are also convex. The claim above could be restated as: "for any N, any convex shape allows convex fair partitioning into N pieces".

If the claim is indeed true, how could one try to minimize the perimeter of each resulting piece?.

To be honest I don't know for sure if it is possible to divide, say, an equilateral triangle into, say, 5 convex pieces all with same area and same perimeter. Even this simple example appears somewhat tricky although the convexity requirement on the pieces is a strong constraint which makes the claim shaky.

Of course, if the claim gets successfully countered, then, one could relax the claim in various ways and say, say

(1) any convex shape, for any N, can be cut into N pieces, not necessarily convex so that all pieces have same area and same perimeter (this claim looks very plausible as of now).

or else

(2) For any convex shape, there exists some N, so that the shape can be cut into N convex pieces of same area and same perimeter. Perhaps one could say: "some N greater than 2". Well, things seem murky!

I could not find any known result on this - although there has been work on dividing into pieces so that every piece has same area and the same fraction of the outer boundary of the target. The requirement that all pieces should have same perimeter is not very easy to ensure - at least not as easy as ensuring equal areas for them. One does not know ab initio what precise perimeter each piece should have!