Packing problems

Packing in 3-dimensional containers

Different cuboids into a cuboid

Determine the minimum number of cuboid containers (bins) that are required to pack a given set of item cuboids. The rectangular cuboids to be packed can be rotated by 90 degrees on each axis.

Spheres into a Euclidean ball

The problem of finding the smallest ball such that k disjoint open unit balls may be packed inside it has a simple and complete answer in n-dimensional Euclidean space if ${\displaystyle k\le n+1}$, and in an infinite-dimensional Hilbert space with no restrictions. It is worth describing in detail here, to give a flavor of the general problem. In this case, a configuration of k pairwise tangent unit balls is available. People place the centers at the vertices ${\displaystyle a_1,\dots ,a_k}$ of a regular ${\displaystyle (k-1)}$ dimensional simplex with edge 2; this is easily realized starting from an orthonormal basis. A small computation shows that the distance of each vertex from the barycenter is $\sqrt{2(1-\frac{1}{k})}$. Moreover, any other point of the space necessarily has a larger distance from at least one of the k vertices. In terms of inclusions of balls, the k open unit balls centered at ${\displaystyle a_1,\dots ,a_k}$ are included in a ball of radius $r_k:=1+\sqrt{2(1-\frac{1}{k})}$, which is minimal for this configuration.

To show that this configuration is optimal, let ${\displaystyle x_1,\dots ,x_k}$ be the centers of k disjoint open unit balls contained in a ball of radius r centered at a point ${\displaystyle x_0}$. Consider the map from the finite set ${\displaystyle \{x_1,\dots ,x_k\}}$ into ${\displaystyle \{a_1,\dots ,a_k\}}$ taking ${\displaystyle x_j}$ in the corresponding ${\displaystyle a_j}$ for each ${\displaystyle 1\le j\le k}$. Since for all ${\displaystyle 1\le i<j\le k}$, ${\displaystyle \Vert a_i-a_j\Vert =2\le \Vert x_i-x_j\Vert }$ this map is 1-Lipschitz and by the Kirszbraun theorem it extends to a 1-Lipschitz map that is globally defined; in particular, there exists a point ${\displaystyle a_0}$ such that for all ${\displaystyle 1\le j\le k}$ one has ${\displaystyle \Vert a_0-a_j\Vert \le \Vert x_0-x_j\Vert }$, so that also ${\displaystyle r_k\le 1+\Vert a_0-a_j\Vert \le 1+\Vert x_0-x_j\Vert \le r}$. This shows that there are k disjoint unit open balls in a ball of radius r if and only if ${\displaystyle r\ge r_k}$. Notice that in an infinite-dimensional Hilbert space this implies that there are infinitely many disjoint open unit balls inside a ball of radius r if and only if ${\displaystyle r\ge 1+\sqrt{2}}$. For instance, the unit balls centered at ${\displaystyle \sqrt{2}{e}_j}$, where ${\displaystyle \{e_j{\}}_j}$ is an orthonormal basis, are disjoint and included in a ball of radius ${\displaystyle 1+\sqrt{2}}$ centered at the origin. Moreover, for ${\displaystyle r<1+\sqrt{2}}$, the maximum number of disjoint open unit balls inside a ball of radius r is $${\displaystyle \lfloor \frac{2}{2-(r-1{)}^2}\rfloor .}$$

Spheres in a cuboid

People determine the number of spherical objects of given diameter d that can be packed into a cuboid of size ${\displaystyle a\times b\times c}$.

Identical spheres in a cylinder

People determine the minimum height h of a cylinder with given radius R that will pack n identical spheres of radius r (< R). For a small radius R the spheres arrange to ordered structures, called columnar structures.

Polyhedra in spheres

People determine the minimum radius R that will pack n identical, unit volume polyhedra of a given shape.

Packing in 2-dimensional containers

Many variants of 2-dimensional packing problems have been studied.

Packing of circles

People are given n unit circles, and have to pack them in the smallest possible container. Several kinds of containers have been studied:

• Packing circles in a circle - closely related to spreading points in a unit circle with the objective of finding the greatest minimal separation, d_n, between points. Optimal solutions have been proven for n ≤ 14, and n = 19.
• Packing circles in a square - closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, d_n, between points. To convert between these two formulations of the problem, the square side for unit circles will be ${\displaystyle L=2+2/d_n}$. Optimal solutions have been proven for n ≤ 30.
• Packing circles in a rectangle
• Packing circles in an isosceles right triangle - good estimates are known for n < 300.
• Packing circles in an equilateral triangle - Optimal solutions are known for n ≤ 15, and conjectures are available for n ≤ 34.

Packing of squares

People are given n unit squares and have to pack them into the smallest possible container, where the container type varies:

• Packing squares in a square: Optimal solutions have been proven for n from 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100, and any square integer. The wasted space is asymptotically O(a^3/5).
• Packing squares in a circle: Good solutions are known for n ≤ 35.

Packing of rectangles

• Packing identical rectangles in a rectangle: The problem of packing multiple instances of a single rectangle of size (l,w), allowing for 90° rotation, in a bigger rectangle of size (L,W ) has some applications such as loading of boxes on pallets and, specifically, woodpulp stowage. For example, it is possible to pack 147 rectangles of size (137,95) in a rectangle of size (1600,1230).
• Packing different rectangles in a rectangle: The problem of packing multiple rectangles of varying widths and heights in an enclosing rectangle of minimum area (but with no boundaries on the enclosing rectangle's width or height) has an important application in combining images into a single larger image. A web page that loads a single larger image often renders faster in the browser than the same page loading multiple small images, due to the overhead involved in requesting each image from the web server. The problem is NP-complete in general, but there are fast algorithms for solving small instances.

Related fields

In tiling or tessellation problems, there are to be no gaps, nor overlaps. Many of the puzzles of this type involve packing rectangles or polyominoes into a larger rectangle or other square-like shape.

There are significant theorems on tiling rectangles (and cuboids) in rectangles (cuboids) with no gaps or overlaps:

An a × b rectangle can be packed with 1 × n strips if and only if n divides a or n divides b.

de Bruijn's theorem: A box can be packed with a harmonic brick a × a b × a b c if the box has dimensions a p × a b q × a b c r for some natural numbers p, q, r (i.e., the box is a multiple of the brick.)

The study of polyomino tilings largely concerns two classes of problems: to tile a rectangle with congruent tiles, and to pack one of each n-omino into a rectangle.

A classic puzzle of the second kind is to arrange all twelve pentominoes into rectangles sized 3×20, 4×15, 5×12 or 6×10.

Packing of irregular objects

Packing of irregular objects is a problem not lending itself well to closed form solutions; however, the applicability to practical environmental science is quite important. For example, irregularly shaped soil particles pack differently as the sizes and shapes vary, leading to important outcomes for plant species to adapt root formations and to allow water movement in the soil.

The problem of deciding whether a given set of polygons can fit in a given square container has been shown to be complete for the existential theory of the reals.