Packing problems are a class of
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
s in
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
that involve attempting to pack objects together into containers. The goal is to either pack a single container as
densely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-life
packaging
Packaging is the science, art and technology of enclosing or protecting products for distribution, storage, sale, and use. Packaging also refers to the process of designing, evaluating, and producing packages. Packaging can be described as a c ...
, storage and transportation issues. Each packing problem has a dual
covering problem
In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems ...
, which asks how many of the same objects are required to completely cover every region of the container, where objects are allowed to overlap.
In a
bin packing problem, you are given:
* A ''container'', usually a two- or three-dimensional
convex region
In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points in the subset, the subset contains the whole line segment that joins them. Equivalently, a convex set or a convex r ...
, possibly of infinite size. Multiple containers may be given depending on the problem.
* A set of ''objects'', some or all of which must be packed into one or more containers. The set may contain different objects with their sizes specified, or a single object of a fixed dimension that can be used repeatedly.
Usually the packing must be without overlaps between goods and other goods or the container walls. In some variants, the aim is to find the configuration that packs a single container with the maximal
packing density. More commonly, the aim is to pack all the objects into as few containers as possible. In some variants the overlapping (of objects with each other and/or with the boundary of the container) is allowed but should be minimized.
Packing in infinite space
Many of these problems, when the container size is increased in all directions, become equivalent to the problem of packing objects as densely as possible in infinite
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidea ...
. This problem is relevant to a number of scientific disciplines, and has received significant attention. The
Kepler conjecture
The Kepler conjecture, named after the 17th-century mathematician and astronomer Johannes Kepler, is a mathematical theorem about sphere packing in three-dimensional Euclidean space. It states that no arrangement of equally sized spheres filling s ...
postulated an optimal solution for
packing spheres hundreds of years before it was
proven correct by
Thomas Callister Hales. Many other shapes have received attention, including ellipsoids,
Platonic and
Archimedean solid
In geometry, an Archimedean solid is one of the 13 solids first enumerated by Archimedes. They are the convex uniform polyhedra composed of regular polygons meeting in identical vertices, excluding the five Platonic solids (which are compose ...
s
including
tetrahedra
In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all th ...
,
tripods (unions of
cube
In geometry, a cube is a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex. Viewed from a corner it is a hexagon and its net is usually depicted as a cross.
The cube is the only ...
s along three positive axis-parallel rays), and unequal-sphere dimers.
Hexagonal packing of circles
These problems are mathematically distinct from the ideas in the
circle packing theorem
The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in gen ...
. The related
circle packing
In geometry, circle packing is the study of the arrangement of circles (of equal or varying sizes) on a given surface such that no overlapping occurs and so that no circle can be enlarged without creating an overlap. The associated '' packing de ...
problem deals with packing
circle
A circle is a shape consisting of all points in a plane that are at a given distance from a given point, the centre. Equivalently, it is the curve traced out by a point that moves in a plane so that its distance from a given point is cons ...
s, possibly of different sizes, on a surface, for instance the
plane or a
sphere
A sphere () is a geometrical object that is a three-dimensional analogue to a two-dimensional circle. A sphere is the set of points that are all at the same distance from a given point in three-dimensional space.. That given point is the c ...
.
The
counterparts of a circle in other dimensions can never be packed with complete efficiency in
dimension
In physics and mathematics, the dimension of a mathematical space (or object) is informally defined as the minimum number of coordinates needed to specify any point within it. Thus, a line has a dimension of one (1D) because only one coord ...
s larger than one (in a one-dimensional universe, the circle analogue is just two points). That is, there will always be unused space if you are only packing circles. The most efficient way of packing circles,
hexagonal packing, produces approximately 91% efficiency.
Sphere packings in higher dimensions
In three dimensions,
close-packed structures offer the best ''lattice'' packing of spheres, and is believed to be the optimal of all packings. With 'simple' sphere packings in three dimensions ('simple' being carefully defined) there are nine possible definable packings. The 8-dimensional
E8 lattice and 24-dimensional
Leech lattice have also been proven to be optimal in their respective real dimensional space.
Packings of Platonic solids in three dimensions
Cubes can easily be arranged to fill three-dimensional space completely, the most natural packing being the
cubic honeycomb
The cubic honeycomb or cubic cellulation is the only proper regular space-filling tessellation (or honeycomb) in Euclidean 3-space made up of cubic cells. It has 4 cubes around every edge, and 8 cubes around each vertex. Its vertex figure is a r ...
. No other
Platonic solid
In geometry, a Platonic solid is a convex, regular polyhedron in three-dimensional Euclidean space. Being a regular polyhedron means that the faces are congruent (identical in shape and size) regular polygons (all angles congruent and all e ...
can tile space on its own, but some preliminary results are known.
Tetrahedra
In geometry, a tetrahedron (plural: tetrahedra or tetrahedrons), also known as a triangular pyramid, is a polyhedron composed of four triangular faces, six straight edges, and four vertex corners. The tetrahedron is the simplest of all th ...
can achieve a packing of at least 85%. One of the best packings of regular
dodecahedra is based on the aforementioned face-centered cubic (FCC) lattice.
Tetrahedra and
octahedra together can fill all of space in an arrangement known as the
tetrahedral-octahedral honeycomb
The tetrahedral-octahedral honeycomb, alternated cubic honeycomb is a quasiregular space-filling tessellation (or honeycomb) in Euclidean 3-space. It is composed of alternating regular octahedra and tetrahedra in a ratio of 1:2.
Other names i ...
.
Simulations combining local improvement methods with random packings suggest that the lattice packings for icosahedra, dodecahedra, and octahedra are optimal in the broader class of all packings.
Packing in 3-dimensional containers
Different cuboids into a cuboid
Determine the minimum number of
cuboid
In geometry, a cuboid is a hexahedron, a six-faced solid. Its faces are quadrilaterals. Cuboid means "like a cube", in the sense that by adjusting the length of the edges or the angles between edges and faces a cuboid can be transformed into a c ...
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
disjoint open
unit ball
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (a ...
s may be packed inside it has a simple and complete answer in -dimensional Euclidean space if
, and in an infinite-dimensional
Hilbert space
In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise natural ...
with no restrictions. It is worth describing in detail here, to give a flavor of the general problem. In this case, a configuration of pairwise
tangent
In geometry, the tangent line (or simply tangent) to a plane curve at a given point is the straight line that "just touches" the curve at that point. Leibniz defined it as the line through a pair of infinitely close points on the curve. Mo ...
unit balls is available. Place the centers at the vertices
of a regular
dimensional
simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
with edge 2; this is easily realized starting from an
orthonormal basis
In mathematics, particularly linear algebra, an orthonormal basis for an inner product space ''V'' with finite dimension is a basis for V whose vectors are orthonormal, that is, they are all unit vectors and orthogonal to each other. For examp ...
. A small computation shows that the distance of each vertex from the barycenter is
. Moreover, any other point of the space necessarily has a larger distance from ''at least'' one of the vertices. In terms of inclusions of balls, the open unit balls centered at
are included in a ball of radius
, which is minimal for this configuration.
To show that this configuration is optimal, let
be the centers of disjoint open unit balls contained in a ball of radius centered at a point
. Consider the
map from the finite set
into
taking
in the corresponding
for each
. Since for all
,
this map is 1-
Lipschitz Lipschitz, Lipshitz, or Lipchitz, is an Ashkenazi Jewish (Yiddish/German-Jewish) surname. The surname has many variants, including: Lifshitz ( Lifschitz), Lifshits, Lifshuts, Lefschetz; Lipschitz, Lipshitz, Lipshits, Lopshits, Lipschutz (Lip ...
and by the
Kirszbraun theorem it extends to a 1-Lipschitz map that is globally defined; in particular, there exists a point
such that for all
one has
, so that also
. This shows that there are disjoint unit open balls in a ball of radius
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bic ...
. Notice that in an infinite-dimensional Hilbert space this implies that there are infinitely many disjoint open unit balls inside a ball of radius if and only if
. For instance, the unit balls centered at
, where
is an orthonormal basis, are disjoint and included in a ball of radius
centered at the origin. Moreover, for
, the maximum number of disjoint open unit balls inside a ball of radius is
.
Spheres in a cuboid
Determine the number of spherical objects of given diameter that can be packed into a cuboid of size
.
Identical spheres in a cylinder
Determine the minimum height of a
cylinder
A cylinder (from ) has traditionally been a three-dimensional solid, one of the most basic of curvilinear geometric shapes. In elementary geometry, it is considered a prism with a circle as its base.
A cylinder may also be defined as an ...
with given radius that will pack identical spheres of radius . For a small radius the spheres arrange to ordered structures, called
columnar structures.
Polyhedra in spheres
Determine the minimum radius that will pack identical, unit
volume
Volume is a measure of occupied three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch). ...
polyhedra
In geometry, a polyhedron (plural polyhedra or polyhedrons; ) is a three-dimensional shape with flat polygonal faces, straight edges and sharp corners or vertices.
A convex polyhedron is the convex hull of finitely many points, not all on ...
of a given shape.
Packing in 2-dimensional containers
Many variants of 2-dimensional packing problems have been studied. See the linked pages for more information.
Packing of circles
You are given
unit circle
In mathematics, a unit circle is a circle of unit radius—that is, a radius of 1. Frequently, especially in trigonometry, the unit circle is the circle of radius 1 centered at the origin (0, 0) in the Cartesian coordinate system in the Eucli ...
s, 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, , between points. Optimal solutions have been proven for , and .
*
Packing circles in a square - closely related to spreading points in a unit square with the objective of finding the greatest minimal separation, , between points. To convert between these two formulations of the problem, the square side for unit circles will be
.
Optimal solutions have been proven for .
*
Packing circles in an isosceles right triangle - good estimates are known for .
*
Packing circles in an equilateral triangle - Optimal solutions are known for , and
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in ...
s are available for .
Packing of squares
You are given
unit square
In mathematics, a unit square is a square whose sides have length . Often, ''the'' unit square refers specifically to the square in the Cartesian plane with corners at the four points ), , , and .
Cartesian coordinates
In a Cartesian coordin ...
s 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 from 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100, and any
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
. The wasted space is asymptotically .
*
Packing squares in a circle: Good solutions are known for .
Packing of rectangles
* Packing identical rectangles in a rectangle: The problem of packing multiple instances of a single
rectangle
In Euclidean plane geometry, a rectangle is a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that all of its angles are equal (360°/4 = 90°); or a parallelogram contain ...
of size , allowing for 90° rotation, in a bigger rectangle of size has some applications such as loading of boxes on pallets and, specifically,
woodpulp
Pulp is a lignocellulosic fibrous material prepared by chemically or mechanically separating cellulose fibers from wood, fiber crops, waste paper, or rags. Mixed with water and other chemical or plant-based additives, pulp is the major raw mate ...
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
Area is the quantity that expresses the extent of a region on the plane or on a curved surface. The area of a plane region or ''plane area'' refers to the area of a shape or planar lamina, while '' surface area'' refers to the area of an op ...
(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 computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
in general, but there are fast algorithms for solving small instances.
Related fields
In tiling or
tessellation
A tessellation or tiling is the covering of a surface, often a plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety of ...
problems, there are to be no gaps, nor overlaps. Many of the puzzles of this type involve packing rectangles or
polyomino
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge. It is a polyform whose cells are squares. It may be regarded as a finite subset of the regular square tiling.
Polyominoes have been used in pop ...
es into a larger rectangle or other square-like shape.
There are significant
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of t ...
s 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
In a 1969 paper, Dutch mathematician Nicolaas Govert de Bruijn proved several results about packing congruent rectangular bricks (of any dimension) into larger rectangular boxes, in such a way that no space is left over. One of these results is n ...
: A box can be packed with a
harmonic brick
In a 1969 paper, Dutch mathematician Nicolaas Govert de Bruijn proved several results about packing congruent rectangular bricks (of any dimension) into larger rectangular boxes, in such a way that no space is left over. One of these results is n ...
''a'' × ''a b'' × ''a b c'' if the box has dimensions ''a p'' × ''a b q'' × ''a b c r'' for some
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s ''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
pentomino
Derived from the Greek word for ' 5', and " domino", a pentomino (or 5-omino) is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge. When rotations and reflections are not considered ...
es 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
polygon
In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed '' polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two ...
s can fit in a given square container has been shown to be complete for the
existential theory of the reals In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form
\exists X_1 \cdots \exists X_n \, F(X_1,\dots, X_n),
where the variables X_i are interpre ...
.
[.]
See also
*
Set packing Set packing is a classical NP-complete problem in computational complexity theory and combinatorics, and was one of Karp's 21 NP-complete problems. Suppose one has a finite set ''S'' and a list of subsets of ''S''. Then, the set packing problem asks ...
*
Bin packing problem
*
Slothouber–Graatsma puzzle
*
Conway puzzle
Conway's puzzle, or blocks-in-a-box, is a packing problem using rectangular blocks, named after its inventor, mathematician John Conway. It calls for packing thirteen 1 × 2 × 4 blocks, one 2 × 2 × 2 block, one 1 × 2 × 2 block, and three 1 � ...
*
Tetris
''Tetris'' (russian: link=no, Тетрис) is a puzzle video game created by Soviet software engineer Alexey Pajitnov in 1984. It has been published by several companies for multiple platforms, most prominently during a dispute over the appro ...
*
Covering problem
In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure 'covers' another, or how large the structure has to be to do that. Covering problems are minimization problems ...
*
Knapsack problem
The knapsack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit a ...
*
Tetrahedron packing In geometry, tetrahedron packing is the problem of arranging identical regular tetrahedron, tetrahedra throughout three-dimensional space so as to fill the maximum possible fraction of space.
Currently, the best lower bound achieved on the optima ...
*
Ellipsoid packing In geometry, ellipsoid packing is the problem of arranging identical ellipsoid throughout three-dimensional space to fill the maximum possible fraction of space.
The currently densest known packing structure for ellipsoid has two candidates,
a simp ...
*
Cutting stock problem
In operations research, the cutting-stock problem is the problem of cutting standard-sized pieces of stock material, such as paper rolls or sheet metal, into pieces of specified sizes while minimizing material wasted. It is an optimization problem ...
*
Kissing number problem
In geometry, the kissing number of a mathematical space is defined as the greatest number of non-overlapping unit spheres that can be arranged in that space such that they each touch a common unit sphere. For a given sphere packing (arrangement o ...
*
Close-packing of equal spheres
In geometry, close-packing of equal spheres is a dense arrangement of congruent spheres in an infinite, regular arrangement (or lattice). Carl Friedrich Gauss proved that the highest average density – that is, the greatest fraction of space o ...
*
Random close pack
*
Strip packing problem The strip packing problem is a 2-dimensional geometric minimization problem.
Given a set of axis-aligned rectangles and a strip of bounded width and infinite height, determine an overlapping-free packing of the rectangles into the strip minimizing ...
Notes
References
*
*
External links
Optimizing Three-Dimensional Bin PackingAPI for 3D bin packing3D Boxes and Cylinders packing with telescopingMany puzzle books as well as mathematical journals contain articles on packing problems.
www.packomania.comA site with tables, graphs, calculators, references, etc.
"Box Packing"by
Ed Pegg, Jr.
Edward Taylor Pegg Jr. (born December 7, 1963) is an expert on mathematical puzzles and is a self-described recreational mathematician. He wrote an online puzzle column called Ed Pegg Jr.'s ''Math Games'' for the Mathematical Association of Am ...
, the
Wolfram Demonstrations Project, 2007.
Best known packings of equal circles in a circle, up to 1100
Circle packing challenge problem in Python
{{Packing problem