More On Cutting Polygons And Stuff
Am keying in some more thoughts on the general issue of cutting polygons into pieces.
Here and here , I speculated on dividing a convex polygon into equal area pieces using least 'knife action'. I now wonder what would happen if the job is to divide a convex polygon (and in general any polygon) in a general ratio a:b. Will the result provided by Koutsoupias et al in "On the Optimal Bisection of a Polygon" (available for download at http://cgi.di.uoa.gr/~elias/publications/ ) go thru essentially unchanged here as well? Will the cuts remain arcs? For instance, even dividing a circular disc in the ratio, say, 1:2 could be interesting. I am not sure if the cut line will be an arc which meets the boundary of the disc to be cut at right angles at both ends - if such is indeed the case for any partitioning ratio, it would be nice!
Aside: The above paper also proves a lemma (in a way I have not been able to fathom yet) which implies: *any* convex polygon can be *optimally* equally divided by a single cut resulting in exactly two pieces. Must say this *feels* nicely intuitive. Wonder if there is any simpler proof for this.
Now, moving on to three dimensions ( I am literally out of my depth here, as of now), one could ask: If a polyhedron or polytope has to be divided into equal volume pieces (or pieces in any general ratio), what will the cutting surface(s) look like?
Here and here , I speculated on dividing a convex polygon into equal area pieces using least 'knife action'. I now wonder what would happen if the job is to divide a convex polygon (and in general any polygon) in a general ratio a:b. Will the result provided by Koutsoupias et al in "On the Optimal Bisection of a Polygon" (available for download at http://cgi.di.uoa.gr/~elias/publications/ ) go thru essentially unchanged here as well? Will the cuts remain arcs? For instance, even dividing a circular disc in the ratio, say, 1:2 could be interesting. I am not sure if the cut line will be an arc which meets the boundary of the disc to be cut at right angles at both ends - if such is indeed the case for any partitioning ratio, it would be nice!
Aside: The above paper also proves a lemma (in a way I have not been able to fathom yet) which implies: *any* convex polygon can be *optimally* equally divided by a single cut resulting in exactly two pieces. Must say this *feels* nicely intuitive. Wonder if there is any simpler proof for this.
Now, moving on to three dimensions ( I am literally out of my depth here, as of now), one could ask: If a polyhedron or polytope has to be divided into equal volume pieces (or pieces in any general ratio), what will the cutting surface(s) look like?
posted by R.Nandakumar @ 11:33 PM
3 Comments:
At 9:47 AM,
Anonymous said…
Could you give the number of the lemma? I've located the paper, but could not find which lemma.
At 8:48 PM,
R.Nandakumar said…
vishnu,
actually, the statement of the main theorem itself (on page 1) says the number of cuts is c+1 where c is the number of concavities. at the end of the proof of lemma 2, there is again the remark: "...the above lemma suggests the upper bound of c+1 of the number of circular arcs..."
since for any convex polygon c =0, we could infer one cut suffices.
again, thanks for your interest. look forward to further inputs from you.
At 7:27 AM,
R.Nandakumar said…
actually, it appears quite easy to see that any convex polygon can be divided into two equal pieces with some single straight line cut - not arc cut but that is a matter of detail.
take any line that begins at a point P on the boundary of the given convex polygon and ends at a point Q on the boundary. this line PQ divides the polygon into two pieces in the area ratio say a:b (ratio between pieces to the left of PQ and to the right). simply rotate the line by 180 degrees about any point in its interior. at the end of this rotation, the line divides the polygon in the area ratio b:a which is reciprocal of the initial ratio between pieces to the left and right. obviously, somewhere in the middle of the rotation, the ratio between the pieces to the left and right would have been 1:1, by continuity.
Post a Comment
<< Home