A Conjecture Debunked - And Some More...
This is in continuation of the previous post here.
A speculative conjecture was made there: For *any* convex shape to be partitioned int N equal area pieces (positive integer N), so that the minimum total perimeter of the pieces is minimized, *all* pieces (they need not be identical in appearence to each other) must be necessarily *convex*.
This is invalid. A paper by Koutsoupias, Papadimitriou and Sideri titled "On the Optimal Bisection of a Polygon" (available for download at http://cgi.di.uoa.gr/~elias/publications/ ) has the following, rather straightforward counter-example: if an equilateral triangle is to be cut into two equal area pieces (N=2) with minimum cut-length, the cut is not a straight line but an *arc* centered on one of the vertices.
The above paper proves a result: If any polygon (not necessarily convex) has to be cut into two (not necessarily connected) equal area sets with least total cut-length, the cuts are arcs which meet the boundary of the polygon orthogonally.
However, if the polygon has to be cut into N (rather than 2) equal area pieces, the cuts do not necessarily begin and end at the boundary of the 'target'. In this general N>2 case, I have come to know that the cuts, if and when they meet in the interior of the polygon, do so at *120 degrees*. The source which revealed this has not specified if the cuts remain arcs.
I find this result (I do not know of a proof) mysterious and am searching for more details now. For a start, one can infer that the cuts meet three (and no more) at a meeting point in the interior, for *any* polygon being partitioned ...
Incidentally, after the previous conjecture was invalidated, I sort of 'pushed the envelope' and modified it thus: for any convex shape to be cut into N equal area pieces with least cut-length, for sufficiently large N (say, some function of the number of sides in the polygon), the cuts are straight lines. I am not clear if this 120 degree requirement and related facts invalidate this guess as well!
A speculative conjecture was made there: For *any* convex shape to be partitioned int N equal area pieces (positive integer N), so that the minimum total perimeter of the pieces is minimized, *all* pieces (they need not be identical in appearence to each other) must be necessarily *convex*.
This is invalid. A paper by Koutsoupias, Papadimitriou and Sideri titled "On the Optimal Bisection of a Polygon" (available for download at http://cgi.di.uoa.gr/~elias/publications/ ) has the following, rather straightforward counter-example: if an equilateral triangle is to be cut into two equal area pieces (N=2) with minimum cut-length, the cut is not a straight line but an *arc* centered on one of the vertices.
The above paper proves a result: If any polygon (not necessarily convex) has to be cut into two (not necessarily connected) equal area sets with least total cut-length, the cuts are arcs which meet the boundary of the polygon orthogonally.
However, if the polygon has to be cut into N (rather than 2) equal area pieces, the cuts do not necessarily begin and end at the boundary of the 'target'. In this general N>2 case, I have come to know that the cuts, if and when they meet in the interior of the polygon, do so at *120 degrees*. The source which revealed this has not specified if the cuts remain arcs.
I find this result (I do not know of a proof) mysterious and am searching for more details now. For a start, one can infer that the cuts meet three (and no more) at a meeting point in the interior, for *any* polygon being partitioned ...
Incidentally, after the previous conjecture was invalidated, I sort of 'pushed the envelope' and modified it thus: for any convex shape to be cut into N equal area pieces with least cut-length, for sufficiently large N (say, some function of the number of sides in the polygon), the cuts are straight lines. I am not clear if this 120 degree requirement and related facts invalidate this guess as well!
posted by R.Nandakumar @ 8:23 PM
0 Comments:
Post a Comment
<< Home