Another Convex Equi-partition Problem
Problem: To divide a 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total length of cuts used is (1) maximized (2) minimized.
Question 1: It appears that for maximum total cut length, the cut lines should not meet in the interior of C. A greedy approach (from C, first cut out a convex region with 1/n of the total area such that the separating cut is the longest possible, then repeat the same process on the remaining piece and so on until we have n equal area pieces) appears to give the optimal answer.
I have no proof or counter example for this greedy algo (note: don't even know a C and n where for max total cut length, the cuts do not all originate from the same point on the boundary).
Question 2: I don't know about minimizing the total cut length. Hopefully, work already done by experts on the Fair Partition front will help.
Update(4th Sept. 2015):
Learnt from Profs. Karasev and Ziegler that the minimizing the total cuts version of the question is most likely much harder and would require heavy machinery to attack.
Have been trying the apparently simpler N=3 case of the maximum-total-cut-length problem; ie. to prove/disprove the guess that the equal area partition into 3 convex pieces of any convex region using max cut length is such that the cuts DO NOT meet in the interior. No luck yet (Just a thought not carried to conclusion: maybe one can show for a convex region C the following function f is concave and so has its max value on the boundary of C: f is the max total cut length of an equipartitioning 3-fan radiating from each point in the region.}
One suspects that there is nothing special about the areas of pieces being equal. Even if the convex region is to be divided into convex pieces with areas in the ratio a:b:c:... using max total cut length, the cuts might again not meet in the interior.
The order in which the pieces are separated would impact the total cut length; a starting guess is: sort a,b,c... and greedily cut out pieces from the smallest area upwards But this need not achieve the most total cut length. Indeed, if the areas of 4 pieces to be cut from a circular disc are in the ratio 1:10:10:1, cutting out the 1's first would not maximize the total cut length it is better to cut out a 10 first. Likewise, separating off pieces in descending order of area would not work in general either.
Maybe one could do the following instead: Sort the areas required. Then from the given region C, cut out a piece with the smallest area (say a1) such that this piece has the highest possible perimeter. This act will give a piece of area a1 and two big convex pieces say C1 and C2. Now from either of C1 amd C2, separate out the next smallest area a2 and so on recursively - again, a greedy approach.
Note: And as usual, higher dimensional analogs of the question could be interesting - eg: a 3D convex region to be cut into convex regions of equal volume such that the total surface area of pieces is maximized/minimized. One can also examine the length of the new edges generated.
Update( 17th September 2015)
A bit of clarity (?) on the N=3 case of maximum-total-cut-length: Let some C be cut into three convex equal area pieces by a fan of 3 rays radiating from any interior point P. Let p_0 be the sum of the perimeters of the three resultant pieces.
Now, let A, B and C be the three points where the three equipartitioning rays from P intersect the boundary of C. Starting from each of these points A,B,C, we have a unique pair of rays which cut C into 3 equal area pieces. Let p_A be the sum of the perimeters of the 3 pieces resulting from rays starting at A. Similarly we have perimeter sums p_B and p_C.
One observes that for any position of P and any A,B,C (satisfying the equal area and convexity constraints), at least one of p_A, p_B and p_C is necessarily greater than p_0 (no neat proof of this bit yet). This would readily imply the total cut length cannot be maximized by a fan of 3 rays starting at an interior point (Note: Sum of the perimeters of the 3 pieces = perimeter of C + 2 X total cut length).
Question 1: It appears that for maximum total cut length, the cut lines should not meet in the interior of C. A greedy approach (from C, first cut out a convex region with 1/n of the total area such that the separating cut is the longest possible, then repeat the same process on the remaining piece and so on until we have n equal area pieces) appears to give the optimal answer.
I have no proof or counter example for this greedy algo (note: don't even know a C and n where for max total cut length, the cuts do not all originate from the same point on the boundary).
Question 2: I don't know about minimizing the total cut length. Hopefully, work already done by experts on the Fair Partition front will help.
Update(4th Sept. 2015):
Learnt from Profs. Karasev and Ziegler that the minimizing the total cuts version of the question is most likely much harder and would require heavy machinery to attack.
Have been trying the apparently simpler N=3 case of the maximum-total-cut-length problem; ie. to prove/disprove the guess that the equal area partition into 3 convex pieces of any convex region using max cut length is such that the cuts DO NOT meet in the interior. No luck yet (Just a thought not carried to conclusion: maybe one can show for a convex region C the following function f is concave and so has its max value on the boundary of C: f is the max total cut length of an equipartitioning 3-fan radiating from each point in the region.}
One suspects that there is nothing special about the areas of pieces being equal. Even if the convex region is to be divided into convex pieces with areas in the ratio a:b:c:... using max total cut length, the cuts might again not meet in the interior.
The order in which the pieces are separated would impact the total cut length; a starting guess is: sort a,b,c... and greedily cut out pieces from the smallest area upwards But this need not achieve the most total cut length. Indeed, if the areas of 4 pieces to be cut from a circular disc are in the ratio 1:10:10:1, cutting out the 1's first would not maximize the total cut length it is better to cut out a 10 first. Likewise, separating off pieces in descending order of area would not work in general either.
Maybe one could do the following instead: Sort the areas required. Then from the given region C, cut out a piece with the smallest area (say a1) such that this piece has the highest possible perimeter. This act will give a piece of area a1 and two big convex pieces say C1 and C2. Now from either of C1 amd C2, separate out the next smallest area a2 and so on recursively - again, a greedy approach.
Note: And as usual, higher dimensional analogs of the question could be interesting - eg: a 3D convex region to be cut into convex regions of equal volume such that the total surface area of pieces is maximized/minimized. One can also examine the length of the new edges generated.
Update( 17th September 2015)
A bit of clarity (?) on the N=3 case of maximum-total-cut-length: Let some C be cut into three convex equal area pieces by a fan of 3 rays radiating from any interior point P. Let p_0 be the sum of the perimeters of the three resultant pieces.
Now, let A, B and C be the three points where the three equipartitioning rays from P intersect the boundary of C. Starting from each of these points A,B,C, we have a unique pair of rays which cut C into 3 equal area pieces. Let p_A be the sum of the perimeters of the 3 pieces resulting from rays starting at A. Similarly we have perimeter sums p_B and p_C.
One observes that for any position of P and any A,B,C (satisfying the equal area and convexity constraints), at least one of p_A, p_B and p_C is necessarily greater than p_0 (no neat proof of this bit yet). This would readily imply the total cut length cannot be maximized by a fan of 3 rays starting at an interior point (Note: Sum of the perimeters of the 3 pieces = perimeter of C + 2 X total cut length).
posted by R.Nandakumar @ 3:54 AM
0 comments
