On a range of Covering and Packing Questions
This post continues from and elaborates on the last post here ...
Not sure if the following broad class of problems is well studied...
To Cover a given convex region C with a specified number N of instances of any specified convex shape - this 'covering shape' could be circle, square, rectangle, isosceles triangle and so forth - such that the total area of the covering shapes is minimum and with no constraint on the sizes of the instances of the covering shape being used.
For example, one uses N squares to cover C such that the sum of the areas of these squares is least but these N squares need not all be of same size.
Other optimizations such as minimizing the sum of the perimeters of the covering shapes also could be thought about.
------------------
One can also seek answers to packing problems in the same spirit - To pack within C N instances of a specified covering shape (not necessarily all equal in size) such that maximum fraction of area of C is filled.
As a specific example, with C as a unit circle, how to pack say 5 squares in it so that max part of the circle is used.
Note: Erich's packing center (https://www2.stetson.edu/~efriedma/packing.html) has several pages on "packing copies to maximize total perimeter". This is the closest online resource I saw to the above questions.
------------------
Update (August 7th 2019):
A bit of speculation, this. Assume that the problem of packing N disks inside any given convex region C to fill the max possible area fraction of C has been solved. Then, in order to solve the problem of N+1 disks inside C, we might not need to discard any of the disks used in the N-case - they may only need to be rearranged so that the remaining part of C contains the largest possible disk and we put that disk as the N+1th one. Perhaps the disk is the only such packing shape for which such a 'greedy' approach works for any C and any N.
Indeed, if C is to be packed with rectangles, as in picture below, where C is a trapezium, the N=1 solution would have to be discarded and a fresh set of rectangles put in for N=2. Such a replacement might not be needed for packing with disks.
Not sure if the following broad class of problems is well studied...
To Cover a given convex region C with a specified number N of instances of any specified convex shape - this 'covering shape' could be circle, square, rectangle, isosceles triangle and so forth - such that the total area of the covering shapes is minimum and with no constraint on the sizes of the instances of the covering shape being used.
For example, one uses N squares to cover C such that the sum of the areas of these squares is least but these N squares need not all be of same size.
Other optimizations such as minimizing the sum of the perimeters of the covering shapes also could be thought about.
------------------
One can also seek answers to packing problems in the same spirit - To pack within C N instances of a specified covering shape (not necessarily all equal in size) such that maximum fraction of area of C is filled.
As a specific example, with C as a unit circle, how to pack say 5 squares in it so that max part of the circle is used.
Note: Erich's packing center (https://www2.stetson.edu/~efriedma/packing.html) has several pages on "packing copies to maximize total perimeter". This is the closest online resource I saw to the above questions.
------------------
Update (August 7th 2019):
A bit of speculation, this. Assume that the problem of packing N disks inside any given convex region C to fill the max possible area fraction of C has been solved. Then, in order to solve the problem of N+1 disks inside C, we might not need to discard any of the disks used in the N-case - they may only need to be rearranged so that the remaining part of C contains the largest possible disk and we put that disk as the N+1th one. Perhaps the disk is the only such packing shape for which such a 'greedy' approach works for any C and any N.
Indeed, if C is to be packed with rectangles, as in picture below, where C is a trapezium, the N=1 solution would have to be discarded and a fresh set of rectangles put in for N=2. Such a replacement might not be needed for packing with disks.
posted by R.Nandakumar @ 1:07 AM
0 Comments:
Post a Comment
<< Home