Lecture
Packing problems — are a class of optimization problems in mathematics that involve attempting to pack objects into containers. The goal of packing is either to pack a single container as densely as possible, or to pack all the objects using as few containers as possible. Many of these problems can relate to packing objects in real life, as well as questions of storage and transportation. Every packing problem has a dual covering problem , which asks how many of a given item are required to completely cover all areas of a container, where the items are allowed to overlap.
A packing problem is defined by:
Usually, in packing, the objects must not intersect each other, and the objects must not intersect the walls of the container. In some variants the goal is to find the configuration that packs a single container with maximum density. More generally, the goal is to pack all the objects into as few containers as possible. In some variants, overlap (of objects with each other and/or with the container's boundary) is allowed, but this overlap must be minimized.
Many of these problems, if the size of the container is increased in all directions, become equivalent to problems of packing objects as densely as possible in infinite Euclidean space. This problem relates to a number of scientific disciplines and receives considerable attention. Kepler's conjecture postulated the optimal solution for sphere packing hundreds of years before it was proven by Thomas Hales . Other shapes have received attention, including ellipsoids , Platonic and Archimedean solids, including tetrahedra and dimers of various spheres .
These problems are mathematically distinct from the ideas in the circle packing theorem. The related circle packing problem deals with packing circles, possibly of different sizes, on a surface, such as a plane or a sphere.
Analogues of the circle in other dimensions cannot be packed with absolute efficiency in dimensions greater than one (in one-dimensional space, the analogue of a circle is simply two points). Thus, there will always be unoccupied space when packing exclusively with circles. The most efficient way of packing circles, hexagonal packing, gives approximately 91% efficiency .
In three-dimensional space, the face-centered lattice gives the optimal sphere packing. It has been proven that the 8-dimensional E8 lattice and the 24-dimensional Leech lattice are optimal in their respective spaces.
Cubes can easily be arranged in three-dimensional space so that they completely fill the space. The most natural packing is the cubic honeycomb . No other regular polyhedron can completely fill space, but some results are known. A tetrahedron can achieve a packing of at least 85%. One of the best packings with regular dodecahedra is based on the aforementioned face-centered cubic lattice.
Tetrahedra and octahedra together can fill all of space in a configuration known as the tetrahedral-octahedral honeycomb .
| Solid | Optimal density of lattice packing |
|---|---|
| icosahedra | 0.836357… |
| dodecahedra | (5+5)/8=0.904508... |
| octahedra | 18/19 = 0.947368… |
Simulations combining local-improvement methods with randomly generated packings suggest that lattice packings for the icosahedron, dodecahedron, and octahedron are optimal even within the broader class of all packings
The problem of finding the smallest ball into which 
open unit balls can be packed without overlap has a simple and complete answer in 
-dimensional Euclidean space, if 
, and in infinite-dimensional Hilbert space — without restriction. It makes sense to describe it here in order to show the general problem. In this case, a configuration of pairwise touching unit balls is possible. Place the centers at the vertices 
of a regular 
-dimensional simplex with edge 2. This can easily be done by starting with an orthonormal basis. Simple calculations show that the distance from any vertex to the centroid equals 
. Moreover, any other point in space has a greater distance to at least one of the 
vertices. In terms of ball inclusion, open unit balls with centers at the points 
fall within a ball of radius 
, which is minimal for such a configuration.
To show that such a configuration is optimal, suppose that 
— are the centers of non-intersecting open unit balls located inside a ball of radius 
centered at the point 0
. Consider the mapping from the finite set 
to 
, mapping 
to 
for all 
. Since for all 
, 
, this mapping is 1-Lipschitz, and by Kirszbraun's theorem it extends to a globally defined 1-Lipschitz mapping. In particular, there exists a point 0
such that for all we have 
, and hence 
. This shows that there exist non-intersecting open unit balls in a ball of radius if and only if 
. Note that in the case of infinite-dimensional Hilbert space, it follows that there exists an infinite number of non-intersecting open unit balls inside a ball of radius if and only if 
. For example, unit balls with centers at 
, where 
— is an orthonormal basis, do not intersect and are contained in a ball of radius 1+2
centered at the origin. Moreover, for 
the maximum number of non-intersecting open unit balls inside a ball of radius r equals 
.
This problem determines the number of spherical objects of a given diameter d that can be packed into a rectangular parallelepiped of size a × b × c.
This problem determines the minimum height h of a cylinder with a given radius R, into which n equal balls of radius r (< R) are packed[10].
Packing n unit circles into the smallest possible circle. This problem is closely related to distributing points in a unit circle in order to achieve the largest minimum distance dn between points.
Optimal solutions have been proven for n≤13 and for n=19.
Packing n unit circles into the smallest possible square. This problem is closely related to distributing points in a unit square in order to achieve the largest minimum distance dn between points . To convert between these two formulations of the problem, the size of the square for unit circles is L=2+2/dn.
Optimal solutions have been proven for n≤30 .
Packing n unit circles into the smallest possible isosceles right triangle. Good approximations are known for n<300.
Packing n unit circles into the smallest possible equilateral triangle. Optimal solutions are known for n<13, and conjectures have been proposed for n<28 .
Packing n unit squares into the smallest possible square.
Optimal solutions have been proven for n=1-10, 14-16, 23-25, 34-36, 62-64, 79-81, 98-100 and any perfect square.
The unfilled space is asymptotically equal to O(a7/11)
Packing n squares into the smallest possible circle.
Minimal solutions:
| Number of squares | Radius of circle |
|---|---|
| 1 | 0.707… |
| 2 | 1.118… |
| 3 | 1.288… |
| 4 | 1.414… |
| 5 | 1.581… |
| 6 | 1.688… |
| 7 | 1.802… |
| 8 | 1.978… |
| 9 | 2.077… |
| 10 | 2.121… |
| 11 | 2.214… |
| 12 | 2.236… |
The problem of packing multiple copies of a single rectangle of size (l,w), with 90° rotation allowed, into a larger rectangle of size (L,W) has several applications, such as loading boxes onto pallets and stacking particle boards.
For example, it is possible to pack 147 rectangles of size 137x95 into a rectangle of size 1600x1230
The problem of packing rectangles with different widths and heights into a rectangle of minimum area (but without any restriction on the width and height of that rectangle) has an important application in assembling images into a single large image. A web page that loads one large image is often processed faster by browsers than one that loads many small images, since a separate request must be made to the server for each image.
An example of a fast algorithm that packs rectangles of varying height and width into a rectangle of minimum area is available here.
In tiling problems there must be neither gaps nor overlaps. Many puzzles of this type use the packing of rectangles or polyominoes into a larger rectangle or another shape close to a square.
There is an important theorem about tiling rectangles (and rectangular parallelepipeds) into rectangles (rectangular parallelepipeds) without gaps or overlaps:
A rectangle a × b can be packed into a strip 1 × n if and only if n is divisible by a or n is divisible by b
De Bruijn's theorem: a rectangular parallelepiped can be packed with a harmonic brick a × a b × a b c, if the parallelepiped has dimensions a p × a b q × a b c r for some natural numbers p, q, r (that is, the parallelepiped is a multiple of the brick).
The study of polyomino tilings largely concerns two classes of problems — tiling a rectangle with congruent tiles, and tiling a rectangle with a set of n-polyomino tiles.
A classic puzzle of the second kind is to arrange all twelve pentomino tiles into rectangles of size 3×20, 4×15, 5×12, or 6×10.
Packing irregular objects is a problem whose solution is unlikely to be possible in closed (analytic) form. However, in the sciences dealing with the natural world, this problem is quite important. For example, irregular soil particles pack in various ways depending on changes in the size and shape of the particles, which leads to significant consequences for plants in terms of root formation and the possibility of water movement in the soil.
Comments