Packing Circles - Questions Galore!
The prime inspiration for this post is 'Erich's Packing Center'. What I have here is a long list of doubts based on the interesting facts given there on the specific problem of packing circles in squares - for a given number N, finding the smallest square which will hold exactly N unit circles. For several examples please see here .
1. It appears that one needs to solve each instance of the problem (each instance given by a certain specified number of circles to be packed in a least square) separately. Are there general rules for characterizing packings like: (i) For what numbers could we always manage with a simple parallelogram lattice of circles (as in the case of 16, 18 and 20 circles for instance) ? (ii) For what numbers will there be one or more 'loose circles' in the packing (circles which can move a finite distance about its position in the packing without violating the square) (7, 11, 17, 21 etc..) ?
Remark: It appears that there are no such rules. Obviously some numbers work well for this 18=4+3+4+3+4 and 20=4+4+4+4+4. But you don't know ahead of time that this translates into an optimal packing.
2. If we allow only simple parallelogram lattices of circles (with one circle per 'unit cell') to be used while packing circles in squares, could we have a general method to find the minimal square given the number of circles to be packed? This becomes relevant if we are automating the packing and can only handle simple lattice arrangements of the circles.
Remark: The hex packing is a lot better than the diamond packing, so for large N this won't be as good - it would be better to place the square over a hex lattice and trap as many circles as possible.
3. If we allow only simple parallelogram lattices but allow the container to be a rectangle with (i) minimum area or (ii) minimum perimeter, do we have a single general algorithm for any number of circles to be packed?
Remark: It appears this is unexplored territory.
4. And if we allow the container to be other than a square, can the 'loose circles' /non-lattice arrangements be always avoided for some specific type of container? Even in the 'Circles in Circles' page at the 'Packing Center', loose circles are seen for some numbers.
Remark: "thin" enough containers won't have this problem, But it is hard to see any shape that won't have this problem when scaled up large enough.
5. It is possible that there is a connection between selections of N circles from a fixed lattice to polyominoes with N squares - the number of different N-ominoes is exponential. The number of candidate circle arrangements perhaps is probably exponential as well.
Maybe we could have ways to filter down the number of candidate selections of circles to a polynomial in N - perhaps by eliminating circle selections corresponding to long 'polyominoes' if one is looking for the smallest square.
Remark: One needs to find a good way to prune the tree of polyominoes to only consider ones that are fat instead of skinny. Perhaps a more general idea of convexity, while making sure the width and height don't differ by 2 or more..
6. I would also like to know if there are any problems in this area which are known to be NP-complete. Finding the minimal square for a given number of circles seems to be far more complex than NP-complete since one cannot choose from a discrete set of options.
8. Here is an apparently simpler problem: Given a known and fixed parallelogram lattice of circles and a number N. Find the minimal area/ perimeter rectangle (or square) that can be placed on the lattice so that it 'traps' N circles fully within it. Does this or some other variant of the main packing problem enable a reduction of the problem to choosing from a discrete set of candidates?
Remark: One needs to see how to reduce the problem to finitely many cases.
1. It appears that one needs to solve each instance of the problem (each instance given by a certain specified number of circles to be packed in a least square) separately. Are there general rules for characterizing packings like: (i) For what numbers could we always manage with a simple parallelogram lattice of circles (as in the case of 16, 18 and 20 circles for instance) ? (ii) For what numbers will there be one or more 'loose circles' in the packing (circles which can move a finite distance about its position in the packing without violating the square) (7, 11, 17, 21 etc..) ?
Remark: It appears that there are no such rules. Obviously some numbers work well for this 18=4+3+4+3+4 and 20=4+4+4+4+4. But you don't know ahead of time that this translates into an optimal packing.
2. If we allow only simple parallelogram lattices of circles (with one circle per 'unit cell') to be used while packing circles in squares, could we have a general method to find the minimal square given the number of circles to be packed? This becomes relevant if we are automating the packing and can only handle simple lattice arrangements of the circles.
Remark: The hex packing is a lot better than the diamond packing, so for large N this won't be as good - it would be better to place the square over a hex lattice and trap as many circles as possible.
3. If we allow only simple parallelogram lattices but allow the container to be a rectangle with (i) minimum area or (ii) minimum perimeter, do we have a single general algorithm for any number of circles to be packed?
Remark: It appears this is unexplored territory.
4. And if we allow the container to be other than a square, can the 'loose circles' /non-lattice arrangements be always avoided for some specific type of container? Even in the 'Circles in Circles' page at the 'Packing Center', loose circles are seen for some numbers.
Remark: "thin" enough containers won't have this problem, But it is hard to see any shape that won't have this problem when scaled up large enough.
5. It is possible that there is a connection between selections of N circles from a fixed lattice to polyominoes with N squares - the number of different N-ominoes is exponential. The number of candidate circle arrangements perhaps is probably exponential as well.
Maybe we could have ways to filter down the number of candidate selections of circles to a polynomial in N - perhaps by eliminating circle selections corresponding to long 'polyominoes' if one is looking for the smallest square.
Remark: One needs to find a good way to prune the tree of polyominoes to only consider ones that are fat instead of skinny. Perhaps a more general idea of convexity, while making sure the width and height don't differ by 2 or more..
6. I would also like to know if there are any problems in this area which are known to be NP-complete. Finding the minimal square for a given number of circles seems to be far more complex than NP-complete since one cannot choose from a discrete set of options.
8. Here is an apparently simpler problem: Given a known and fixed parallelogram lattice of circles and a number N. Find the minimal area/ perimeter rectangle (or square) that can be placed on the lattice so that it 'traps' N circles fully within it. Does this or some other variant of the main packing problem enable a reduction of the problem to choosing from a discrete set of candidates?
Remark: One needs to see how to reduce the problem to finitely many cases.
posted by R.Nandakumar @ 9:13 AM
0 Comments:
Post a Comment
<< Home