Cutting a Polygonal Cake
This post is NOT on the 'Cake Cutting Algorithms', which have had a history of development starting with Steinhaus et al in the '40s - and still continuing...
We (Ramana Rao and self) have spent some time looking at the following different optimization problem: Given a polygon (which could be arbitrarily complex although for the time being, we assume it has no holes). We are interested in cutting it into two equal area sets of polygonal pieces using the least number of straight line cuts (a cut is that portion of a line interescting the polygon between an entry into the polygon and the next exit. so there could be multiple cuts along the same line, they all count as different cuts).
It may be remarked upfront that if the polygon is sufficiently complex it cannot be cut into two equal area pieces with a single straight cut. For example, let the polygon have 3 wavy and winding 'arms' all of equal area, meeting at a small central 'node' (we could call this polygon a 'triopus'). This cannot be cut into two equal area pieces by ANY line. It can be cut with two lines into one set of two pieces and another set with a single piece, both having same area.
Indeed, applying this triopus idea recursively, we could think of polygons which require arbitraily large numbers of straight line cuts to break into a a set of pieces and leaving a single piece so that the single piece exactly equals in area the set of pieces ie both are half of the total area of the original polygon.
As far as I know, not much work has been done on such equipartition of polygons using the least number of straight line cuts. There has been work on reducing the total LENGTH of the straight line cuts used (and on using arcs instead of straight lines to cut the polygon and minimizing the sum of arc lengths) but not on optimizing their NUMBER.
It appears that one needs some data structure to represent how the polygon's area is distributed. This data structure should support some equipartition algorithm....
A (hopefully simpler) subproblem: Given a polygon, decide if it can be cut with SOME single line into two pieces of the same area. Solving this could provide some insight into the main problem above.
Even this subproblem in general does not seem to be a discrete problem - the area of the polygon is continuously distributed;and it is probably not possible for this distribution to be captured by a discrete data structure like a 'standard' tree or graph. Moreover thru any point in the interior of the polygon there is an infinity of cuts that could possibly be made.
We (Ramana Rao and self) have spent some time looking at the following different optimization problem: Given a polygon (which could be arbitrarily complex although for the time being, we assume it has no holes). We are interested in cutting it into two equal area sets of polygonal pieces using the least number of straight line cuts (a cut is that portion of a line interescting the polygon between an entry into the polygon and the next exit. so there could be multiple cuts along the same line, they all count as different cuts).
It may be remarked upfront that if the polygon is sufficiently complex it cannot be cut into two equal area pieces with a single straight cut. For example, let the polygon have 3 wavy and winding 'arms' all of equal area, meeting at a small central 'node' (we could call this polygon a 'triopus'). This cannot be cut into two equal area pieces by ANY line. It can be cut with two lines into one set of two pieces and another set with a single piece, both having same area.
Indeed, applying this triopus idea recursively, we could think of polygons which require arbitraily large numbers of straight line cuts to break into a a set of pieces and leaving a single piece so that the single piece exactly equals in area the set of pieces ie both are half of the total area of the original polygon.
As far as I know, not much work has been done on such equipartition of polygons using the least number of straight line cuts. There has been work on reducing the total LENGTH of the straight line cuts used (and on using arcs instead of straight lines to cut the polygon and minimizing the sum of arc lengths) but not on optimizing their NUMBER.
It appears that one needs some data structure to represent how the polygon's area is distributed. This data structure should support some equipartition algorithm....
A (hopefully simpler) subproblem: Given a polygon, decide if it can be cut with SOME single line into two pieces of the same area. Solving this could provide some insight into the main problem above.
Even this subproblem in general does not seem to be a discrete problem - the area of the polygon is continuously distributed;and it is probably not possible for this distribution to be captured by a discrete data structure like a 'standard' tree or graph. Moreover thru any point in the interior of the polygon there is an infinity of cuts that could possibly be made.
posted by R.Nandakumar @ 4:08 PM
0 Comments:
Post a Comment
<< Home