'(The Blog) With No Name', perhaps best described as a stream of notes and thoughts - 'remembered, recovered and (sometimes) invented'.

Monday, February 27, 2006

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 ) 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!


Post a Comment

<< Home