Packing problems
Packing problems involve the challenge of optimally filling a given space with various shapes or determining how many objects can fit within a specified area. These problems are primarily geometric in nature but can also encompass certain numerical challenges relevant to computer science. A key aspect of geometric packing problems is to arrange shapes without overlapping, minimizing leftover space. Classic examples include fitting circles in a plane, where the most efficient arrangement, known as the honeycomb formation, achieves about 90.7% utilization.
In addition to geometric packing, there are recreational packing puzzles, where solvers fit specific shapes into a larger shape, such as the Tangram puzzle from ancient China. Related to packing problems are covering problems, which focus on completely covering an area with overlapping shapes, like placing security guards efficiently in a region. Furthermore, packing problems extend into the realm of computer science through knapsack problems, where the objective is to maximize value within weight or space constraints, illustrating the intersection of mathematics and practical applications. Research continues to explore variations and generalizations of these packing challenges, making it a vibrant area of study.
Packing problems
- SUMMARY: Packing problems challenge the solver to optimally fill a given space or determine how many objects of some type may fit in a space.
The name “packing problems” has been given to a variety of mathematical problems in both “serious” and “recreational” mathematics. Packing problems are mainly geometric but the term is sometimes also applied to certain numerical problems important to computer science. The distinguishing feature of a geometric packing problem is the objective to position a family of shapes with no overlap and a minimal amount of leftover space.
If a baker has rolled out a certain sheet of dough and has a certain size and shape of cookie cutter, how should the shapes be cut to leave as little wasted dough as possible? How many tennis balls will fit in a very large box? These are packing problems of the most fundamental type. The most thoroughly studied case is that of packing identical spheres (circles in the two-dimensional case or hyperspheres in the four-dimensional—or more—space) in Euclidean space. The most efficient way to pack circles in the plane is to surround each circle with six others in a honeycomb formation, filling about 90.7 percent of the plane. It was conjectured by German astronomer and mathematician Johannes Kepler that a similarly symmetric arrangement of spheres (filling about 74 percent of space) is optimal in three dimensions. This conjecture was generally considered to have been proved by American mathematician Thomas Hales in 1998. Hales’s proof of Kepler’s conjecture relies on large-scale computer calculation and represents an important example of a well-studied mathematical problem that is “solved,” but for which no hand-checked proof is known.
There is much potential for generalization. There is already much unknown for hyperspheres in four dimensions; other important variations include considering spheres of varying sizes, considering non-Euclidean geometry, and using different shapes instead of spheres. There is significant, active research along all of these lines.
Packing Puzzles
The above type of problem has been studied both by professional mathematicians and recreational mathematicians, but there is another category of packing problem particular to the recreational mathematician (and to the puzzle enthusiast). In these packing puzzles, the solver tries to fit a collection of shapes into a larger shape; typically, the pieces are of a sort that fits together exactly (for example, packing rectangles into a rectangle rather than packing circles into a square). An old puzzle is to determine, for each n, how large a square is needed to accommodate a 1×1 square, a 2×2 square, a 3×3 square,…, and an n×n square. The oldest known problem of this type is the Tangram puzzle that originated in ancient China, a set of seven simple shapes that can be rearranged to perfectly fill a square (and many other shapes). In the twentieth century, a wide range of packing puzzles involving polyominos (shapes made by gluing together unit squares along their edges) have enjoyed considerable popularity. Packing puzzles can also be posed in three dimensions. Three particularly popular and interesting examples involving blocks illustrate the concept well. The Slothouber–Graatsma puzzle, named after architects Jan Slothouber and William Graatsma, is to pack a 3×3×3 cube with six 1×2×2 blocks (leaving three 1×1×1 holes). The Conway puzzle, named after mathematician John Conway, is to fill a 5×5×5 cube with 13 1×2×4 blocks, one 2×2×2 block, one 1×2×2 block, and three 1×1×3 blocks. A harder puzzle is to pack 41 1×2×4 blocks into a 7×7×7 cube (leaving 15 1×1×1 holes).
Covering Problems
A class of problems closely related to the first type of packing problem discussed are so-called covering problems. Covering problems are “dual” to packing problems; instead of positioning non-overlapping copies of a shape in a region with minimal leftover space (as in a packing problem), the solver positions overlapping copies of a shape so that they completely cover a region with minimal overlap. For example, how many circles of radius 1 does the solver need to completely cover a circle of radius 10? Covering problems have historically received less attention than packing problems, perhaps because packing problems correspond more obviously to physical situations. Nonetheless, covering problems have applications: for example, in designing satellite or cellular networks. Covering a large region as efficiently as possible with circles corresponds to placing security guards in a large area as efficiently as possible so that each point is within a fixed distance of at least one guard.
Packing Problems in Computer Science
Another class of packing problems, the so-called knapsack problems, is numerical (rather than geometric) in nature. A typical example is sometimes called the “Aladdin’s saddlebag problem.”
Aladdin is in a cave full of a variety of treasures: gold, silver, rubies, diamonds, rare books, and other valuable objects. Each type of object takes up a certain amount of space in Aladdin’s saddlebags, weighs a certain amount, and has a certain value. The problem is to decide how to get the most valuable hoard possible, if there is a limited amount of space and if Aladdin’s mule can carry only a limited amount of weight. If the solver thinks of the quantities as continuous (if it makes sense in context to take exactly as much gold as is wanted), then this is a classical instance of linear programming, a powerful and efficient technique in applied mathematics.
On the other hand, if the quantities are discrete (for example, if the gold is in large bars, and Aladdin cannot take more than two bars but less than three), then the problem is, in general, very difficult. Indeed, the simplest version of the discrete knapsack problem is already believed to be computationally quite hard. In this problem, a list of integers is given as well as a large target integer. The goal is to achieve the target as a sum of integer multiples of the given numbers. Any progress toward finding more efficient solving methods or toward showing that the current methods are optimal would be extremely significant in the field of computer science.
Bibliography
Baosu Guo, et al. “Two-Dimensional Irregular Packing Problems: A Review.” Frontiers in Mechanical Engineering, vol. 8, 2022, doi.org/10.3389/fmech.2022.966691. Accessed 19 Nov. 2024.
Friedman, Erich. “Erich’s Packing Center.” erich-friedman.github.io/packing. Accessed 19 Nov. 2024.
Golomb, Solomon. Polyominoes: Puzzles, Patterns, Problems, and Packings. Princeton UP, 1994.
Kellerer, Hans, et al. Knapsack Problems. Springer, 2004.
Posamentier, Alfred S., et al. Geometry in Our Three-Dimensional World. World Scientific Publishing Co. Pte. Ltd., 2022.
Szpiro, George. Kepler’s Conjecture: How Some of the Greatest Minds in History Helped Solve One of the Oldest Math Problems in the World. Wiley, 2003.