Geometric Packing Problems (10/19/2001)



Prepared by:

Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451

Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)



Given one shape X how and when can one pack identical copies of this shape into another shape Y? Here the use of the word pack means that we are allowed to have the packing shapes overlap one another only on their boundaries (perimeter) and that no part of the packing shape can fall outside the shape Y into which we are trying to pack it. However, we do allow the shapes X to have space between them, so that some points of Y are not covered by the shapes of type X.

Examples:

1. Pack squares into a square

2. Pack squares into a rectangle

3. Pack rectangles into a rectangle

4. Pack rectangles into a square

In these examples if the dimensions of the sets X and the set Y are "compatible" then the packing can be carried out so that no space in Y is uncovered. Thus, one can pack 1x2 rectangles (also known as a domino) into a 4x4 square so that no part of the square is uncovered. However, we can not pack 1x2 rectangles into a 3x5 square, without some space in the square being uncovered. This can be seen by a simple area argument. The area of a 3x5 square is 15 so something of area two (1x2 rectangles have area two) can not completely cover such a square.

A classical problem in combinatorics asks whether or not one can pack 1x2 rectangles into an 8x8 chessboard with two opposite corners (those at the end of a diagonal) removed. It may seem that it would be possible to do this since the area to be covered is 62, so conceivably 31 dominoes could cover the board. However, a domino with one square colored white and the other colored black can not cover the chessboard with diagonally opposite squares removed since these two squares in a coloring of the chessboard where adjacent squares get contrasting colors are the same color! The chessboard with these two squares removed has unequal numbers of black and white squares. Thus, the packing is not possible! Having seen this result it is interesting to consider the following problem: if one removes two square of opposite color from the standard coloring of the 8x8 chessboard, can one over the resulting "board" with 31 dominoes? Ralph Gomory has given a proof of the remarkable fact that this is always possible. David Klarner has exploited the idea of cleaverly coloring the squares of a chessboard to resolve a variety of packing problems.

Some changes in wording can result in problems which provide dramatically fruitful mathematics. For example, consider the seeming simple problem of packing squares all with different side lengths into another square without any space left over. This problem and its many variants has surprisingly rich ramifications.

Examples:

5. Pack squares into a circle.

6. Pack circles into a square.

7. Pack circles into a circle.

This last packing problem has some interesting applications. Imagine one has a collection of cylindrical wires (think of fiber optic cable) that are to be arranged parallel to each other inside a large protecting sheath. Paying attention to what is going on only in cross-section, we have the problem of packing circles into a circular shape. Clearly, we have room left over when pack circles into a circle, however, it is obviously of interest to consider the "density" of the packing. By density we mean the ratio of the sum of areas of the packed shapes divided by the area of the shape into which the shapes are being packed. In most situations, the denser the arrangement that can be made, the better.

In the above situation it seems natural to think in terms of a geometric packing problem from the start. However, sometimes the connection is unexpected. For example, suppose that one has a collection of independent tasks. Independent here refers to the fact that the tasks can be done in any order. What is the minimum number of identical machines needed to complete the tasks by time C? (We assume that C is larger than the time needed to complete the longest task.)

This problem can be thought of as a geometric packing problem as follows. Think of the task Ti as being a 1xti rectangle where ti is the time necessary to complete task Ti. The identical machines will correspond to 1xC rectangles where the length of the rectangle is C. It is traditional to refer to these rectangles as bins and the length of the bin as its capacity. In this context, we seek the minimum number of bins of capacity C which into which all the tasks can be packed! The resulting problem is known as the bin packing problem and it turns out that no polynomial time algorithm for finding an optimal packing is known. (The problem is known to be NP-complete.)

The examples so far have considered only the packing of plane figures into plane figures, but clearly there are other possibilities. One can look at packing circular caps on the surface of a sphere or the lateral surface of a cylinder and one can look at problems which involve packing 3-dimensional objects into other 3-dimensional objects.

In both the plane and in 3-space one can consider packing objects into an infinite set Y. What is the densest packing of circles into the plane or sphere into space? The answer to the first problem has been known for some time, but the problem of determining the densest sphere packing in 3-space has only been recently resolved by Thomas Hales. The conjecture, which goes back to Kepler is that the densest way to pack spheres in 3-space is to pack them in the way the grocers typically pack grape fruits: the fruits are laid out on a plane and then the next layer is filled in and so one. Hales' proof like that of the Four Color Theorem requires some calculations to be performed on a computer.

References:

Frederickson, G., Dissections: Plane and Fancy, Cambridge U. Press, New York, 1997.

Golomb, S., Polyominoes, Second Edition, Princeton U. Press, Princeton, 1994.

Honsberger, R., Mathematical Gems, Mathematical Association of America, Washington, 1973.

Klarner, D., (ed.), The Mathematical Gardner, Prindle, Weber & Schmidt, Boston, 1981.

Pach, J., and P. Agarwal, Combinatorial Geometry, John Wiley and Sons, 1995.

Malkevitch, J. et al, For All Practical Purposes, Fifth Edition, W.H. Freeman, New York, 2000.

Tutte, W., Graph Theory As I Have Known It, Oxford U. Press, New York, 1998.


Back to list of tidbits