Geometric Packing Problems (10/19/2001)
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451
Email: firstname.lastname@example.org (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
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.
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.
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,
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
Tutte, W., Graph Theory As I Have Known It, Oxford U. Press, New York, 1998.
Back to list of tidbits