Thoughts On Algorithms, Geometry etc...

Sunday, October 15, 2006

'Fair Partitions' - II

Here we propose a proof for a weaker version of the claim floated in the last post here: Any convex polygon, for any N, can be partitioned into N equal area and equal perimeter pieces, *if the pieces need not be convex*.

Proof for possibility of partitioning a convex polygon into N equal area and perimeter pieces which need not themselves be convex:
1. We first divide the input polygon into N equal area pieces so that exactly 1 'inner' piece *does not* touch the boundary and each of the remaining N -1 pieces share some *finite* boundary with this inner piece (and also divide up the outer boundary of the input polygon among them). We argue how this can always be done a little later.

2. Now, we could deform the common boundary of the inner piece with each of its N-1 neighbors to make all N-1 neighbors have the same perimeter.

If two pieces share an edge, if we introduce some zigzags (with concavities) on that edge, the perimeter of both pieces increase by the same amount - and we can do this without changing their areas. So we note among the N-1 outer pieces, which has the highest perimeter and increase the perimeters of each of the other N-2 outer pieces to this value - by tweaking the common boundary of each of them with the inner piece.

3. Now, all outer pieces have same area and same perimeter. The inner piece also has the same area but a possibly very large perimeter since its boundaries with all outer pieces (except one) have been deformed. We now try to increase the perimeter of all outer pieces to equal this large value.

We note the difference between the perimeter of the inner piece and that of an outer piece - call this quantity d. Then we deform *all* the boundaries between the outer pieces - ie the dividing boundary between outer piece 1 and 2, then the boundary between 2 and 3 and so on - so that the increase in perimeter to both the pieces separated by a given boundary is d/2. So, when all boundaries have been deformed, every outer piece increases its perimeter by d - their areas should be kept constant - which is as desired.

Exception: If after step 2, the inner piece still has *less perimeter* than the common value of the perimeters of the outer pieces, we could tweak the boundary of the input piece with each of the outer ones equally so that every outer piece gains a little perimeter and the innter piece gains N-1 times that much so we could again equalize the perimeters.

A bit remains: how to divide the input convex polygon into N equal area pieces so that one piece is in the middle and the remaining N-1 surround it? For this, we could scale the input polygon by a factor of N and the resulting small polygon can be put somewhere inside the input polygon (this scaling will work if the input polygon is convex). This is the central piece. Then we can walk around the central piece and sweep out N-1 equal area pieces from the remaining 'annular' portion of the input polygon. These N-1 outer pieces are free to be be concave so we could force each of these to share a finite boundary with the inner piece.


Obviously, this approach can cause all the pieces to have very large perimeters and they will also have jagged boundaries. No attempt has been made to minimize the sum of the perimeters of the pieces, which remains to be understood.

We can't see how this argument can be modified to handle the case where the pieces have also to be convex. But this argument does appear to allow us to prove this: "for any N, any (non-convex) polygon can be broken into (non-convex) N pieces all of equal area and perimeter" - the only new idea is to put an thinned down - almost insetted - polygon of area 1/N of the target polygon in the interior of the target (the thinned polygon will be of the same basic skeletal shape as the target and much thinner and will run along the entire length of the target; intuitively, such a polygon can always be found with the required area) - This skeletal polygon will serve as the central polygon in the above proof. The rest of the proof should go thru unchanged. Of course, now we have the question: how to partition a general polygon into general pieces of equal area and equal perimeter *minimizing the perimeter of each*?

For the case when the pieces also have to be convex (the full version of the claim), we tried to find counter-examples like 'dividing a triangle into 5 convex pieces with equal area and perimeter' - no progress yet on that front.


Post a Comment

<< Home