Fair Partitions - 2^N?
We (Ramana Rao and self) consider here a recursive scheme for extending our polygon partitioning conjecture to 2^N. This approach is a variant of a naive recursion on N=2, which does not work - as argued in the post 'Fair Partitions -V':
------------
The conjecture: Given any positive integer N, any convex polygonal region allows partitioning into N convex pieces such that every piece has the same area and perimeter.
------------
Definitions:
-----------
We define a 'diagonal', as a line that divides a convex polygon into two pieces of equal area; their perimeters could be different (the diagonal could be between any two points on the boundary, not necessarily vertices).
Let us further call a line which divides a convex polygon into 2 pieces of equal area and equal perimeter a 'fair bisector'. Of course, a polygon can have just one fair bisector ( eg: for an isosceles triangle with very narrow base), a few or even infinitely many (a square for example) depending on its symmetry.
The Scheme:
----------
Divide input polygon into two equal area pieces by a diagonal; call these pieces A and B. Consider a *fair bisector* of piece A, dividing A into {A1, A2} - where A1 and A2 have equal area and equal perimeter. Likewise consider a fair bisector of B which gives pieces {B1,B2}. Initially, let us say the pair of pieces A1-A2 have higher perimeter than the pair B1-B2.
Rotate the *diagonal* continously; then, the pieces A and B change continuously maintaining equal areas; the two fair bisector lines also keep changing. Finally the diagonal reaches a position that is perfectly reverse of its initial position. Now, pieces A1-A2 have less perimeter than pair B1-B2 - they have merely exchanged their initial positions. By a continuity argument, we have somewhere along the rotation of the diagonal, a state where the two pairs had the same perimeter.
This could settle the conjecture for N= 4. Repeating the recursion, we could even prove the claim for N= 2^n. And if the conjecture could be proved for any number m, this could give a ready extension to N= m * 2^n
Possible Catch:
--------------
It needs to be shown that if a polygon is *continuously changed*, its fair bisector(s) change continuously - by a line segment moving continuously, we mean both its end points move continuously (of course, the length, orientation,etc of the segment as a whole could change).
Take a square and slightly and continously make it asymmetric, keeping its area constant; the new polygon might have only a few or just one fair bisector. this means most fair bisectors have simply *disappeared* by a continous transformation.
A more general case:
Consider a case where the fair bisector of piece A is such that sub-piece A2 covers the bisector entirely, ie. the fair bisector of A connects two edges of the input polygon and does not touch the diagonal which demarkates A and B.
Now let diagonal rotate a little, continuously, keeping the areas of pieces A and B same.Then, perimeter of piece A2 changes while A1 is *unaffected*. Of course, the areas of A1 and A2 remain equal. The net result: a difference just begins to develop between perimeters of A1 and A2.
Now, we need to change the fair bisector between A1 and A2 continuously to cancel out the perimeter difference that has emerged (due to the rotation of the diagonal) between A1 and A2. And we need a guarantee that such a continous change is possible for the entire rotation of the diagonal. What we need to prove is: at least one fair bisector of piece A - call this b(A) - and a fair bisector of piece B - call this b(B) - are such that as diagonal moves by a total of 180 degrees, b(A) continuously moves to b(B); a further movement of 180 of diagonal will cause b(B) to return to b(A).
Note : The new recursive scheme puts a constraint on the fair partitioning, a constraint we were not keen to put:
A general convex partitioning need not have two pieces meet in the interior of the polygon at 180 degrees - they only need to be convex.
In the recursive scheme A1 and A2, if they meet in the interior of polygon, are forced to together form an angle of 180 degrees. In the final partitioning, two pieces A1 and A2 together are forced meet the other two pieces along a straight line.
Update (12-9-08):
----------------
Let us call fair bisectors which are the result of symmetry and which cannot change continuously (and which merely vanish) when a polygon is slightly changed, 'bad bisectors'; those fair bisectors which do change continuously are good ones.
Our scheme seems to need the following to hold: Given two equal area convex polygons which share an edge (and together form a convex polygon). The number of 'good fair bisectors' of both these polygons are necessarily equal.
Indeed, if at a given position of a *diagonal*, the two equal area pieces A and B have different numbers of good fair bisectors, we would begin to doubt if one of A can actually continuously change all the way to one of B (as the diagonal does a 180 degree sweep) and vice versa.
Example:
We could check that the pentagon formed by points:
{(0,0),(6,20),(12,0),(12,-7.947),(12-.92, -19.39075)} has 3 good fair bisectors.
Consider the triangle:
{(0,0),(12-.92, -19.39075),(7,-55.53)}.
This triangle shares an edge with the pentagon, has the same area and together with the pentagon forms a convex polygon.
=> the common edge is a 'diagonal' of the big polygon formed by the pentagon and triangle.
Now, the triangle has only one fair bisector =>
some evidence that when the diagonal moves thru 180 degrees, the fair bisectors *need not* evolve continuously throughout the evolution of the diagonal.
Update (October 22, 2008):
-------------------------
Further experiments have confirmed that the fair bisector(s) of a polygon *may not* evolve continuously as the polygon is continuously deformed (keeping its area constant). But, (crucially!) for this new recursive scheme to work, we do not really need the fair bisectors to keep changing continuously - only the *perimeters of the pieces resulting from the fair bisectors need to change continuously*. In all examples tested so far, the perimeters do change continuously.
No logical proof yet either that the perimeters of pieces resulting from fair bisection of a polygon necessarily change continuously when the polygon itself is changed continuously. Work in progress...
------------
The conjecture: Given any positive integer N, any convex polygonal region allows partitioning into N convex pieces such that every piece has the same area and perimeter.
------------
Definitions:
-----------
We define a 'diagonal', as a line that divides a convex polygon into two pieces of equal area; their perimeters could be different (the diagonal could be between any two points on the boundary, not necessarily vertices).
Let us further call a line which divides a convex polygon into 2 pieces of equal area and equal perimeter a 'fair bisector'. Of course, a polygon can have just one fair bisector ( eg: for an isosceles triangle with very narrow base), a few or even infinitely many (a square for example) depending on its symmetry.
The Scheme:
----------
Divide input polygon into two equal area pieces by a diagonal; call these pieces A and B. Consider a *fair bisector* of piece A, dividing A into {A1, A2} - where A1 and A2 have equal area and equal perimeter. Likewise consider a fair bisector of B which gives pieces {B1,B2}. Initially, let us say the pair of pieces A1-A2 have higher perimeter than the pair B1-B2.
Rotate the *diagonal* continously; then, the pieces A and B change continuously maintaining equal areas; the two fair bisector lines also keep changing. Finally the diagonal reaches a position that is perfectly reverse of its initial position. Now, pieces A1-A2 have less perimeter than pair B1-B2 - they have merely exchanged their initial positions. By a continuity argument, we have somewhere along the rotation of the diagonal, a state where the two pairs had the same perimeter.
This could settle the conjecture for N= 4. Repeating the recursion, we could even prove the claim for N= 2^n. And if the conjecture could be proved for any number m, this could give a ready extension to N= m * 2^n
Possible Catch:
--------------
It needs to be shown that if a polygon is *continuously changed*, its fair bisector(s) change continuously - by a line segment moving continuously, we mean both its end points move continuously (of course, the length, orientation,etc of the segment as a whole could change).
Take a square and slightly and continously make it asymmetric, keeping its area constant; the new polygon might have only a few or just one fair bisector. this means most fair bisectors have simply *disappeared* by a continous transformation.
A more general case:
Consider a case where the fair bisector of piece A is such that sub-piece A2 covers the bisector entirely, ie. the fair bisector of A connects two edges of the input polygon and does not touch the diagonal which demarkates A and B.
Now let diagonal rotate a little, continuously, keeping the areas of pieces A and B same.Then, perimeter of piece A2 changes while A1 is *unaffected*. Of course, the areas of A1 and A2 remain equal. The net result: a difference just begins to develop between perimeters of A1 and A2.
Now, we need to change the fair bisector between A1 and A2 continuously to cancel out the perimeter difference that has emerged (due to the rotation of the diagonal) between A1 and A2. And we need a guarantee that such a continous change is possible for the entire rotation of the diagonal. What we need to prove is: at least one fair bisector of piece A - call this b(A) - and a fair bisector of piece B - call this b(B) - are such that as diagonal moves by a total of 180 degrees, b(A) continuously moves to b(B); a further movement of 180 of diagonal will cause b(B) to return to b(A).
Note : The new recursive scheme puts a constraint on the fair partitioning, a constraint we were not keen to put:
A general convex partitioning need not have two pieces meet in the interior of the polygon at 180 degrees - they only need to be convex.
In the recursive scheme A1 and A2, if they meet in the interior of polygon, are forced to together form an angle of 180 degrees. In the final partitioning, two pieces A1 and A2 together are forced meet the other two pieces along a straight line.
Update (12-9-08):
----------------
Let us call fair bisectors which are the result of symmetry and which cannot change continuously (and which merely vanish) when a polygon is slightly changed, 'bad bisectors'; those fair bisectors which do change continuously are good ones.
Our scheme seems to need the following to hold: Given two equal area convex polygons which share an edge (and together form a convex polygon). The number of 'good fair bisectors' of both these polygons are necessarily equal.
Indeed, if at a given position of a *diagonal*, the two equal area pieces A and B have different numbers of good fair bisectors, we would begin to doubt if one of A can actually continuously change all the way to one of B (as the diagonal does a 180 degree sweep) and vice versa.
Example:
We could check that the pentagon formed by points:
{(0,0),(6,20),(12,0),(12,-7.947),(12-.92, -19.39075)} has 3 good fair bisectors.
Consider the triangle:
{(0,0),(12-.92, -19.39075),(7,-55.53)}.
This triangle shares an edge with the pentagon, has the same area and together with the pentagon forms a convex polygon.
=> the common edge is a 'diagonal' of the big polygon formed by the pentagon and triangle.
Now, the triangle has only one fair bisector =>
some evidence that when the diagonal moves thru 180 degrees, the fair bisectors *need not* evolve continuously throughout the evolution of the diagonal.
Update (October 22, 2008):
-------------------------
Further experiments have confirmed that the fair bisector(s) of a polygon *may not* evolve continuously as the polygon is continuously deformed (keeping its area constant). But, (crucially!) for this new recursive scheme to work, we do not really need the fair bisectors to keep changing continuously - only the *perimeters of the pieces resulting from the fair bisectors need to change continuously*. In all examples tested so far, the perimeters do change continuously.
No logical proof yet either that the perimeters of pieces resulting from fair bisection of a polygon necessarily change continuously when the polygon itself is changed continuously. Work in progress...
posted by R.Nandakumar @ 12:43 AM
0 Comments:
Post a Comment
<< Home