HOME

TheInfoList



OR:

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 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. 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 k \leq n+1, 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 a_1, \dots, a_k of a regular (k-1) 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 \sqrt. 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 a_1, \dots, a_k are included in a ball of radius r_k := 1+\sqrt, which is minimal for this configuration. To show that this configuration is optimal, let x_1, \dots, x_k be the centers of disjoint open unit balls contained in a ball of radius centered at a point x_0. Consider the map from the finite set \ into \ taking x_j in the corresponding a_j for each 1 \leq j \leq k. Since for all 1 \leq i < j \leq k, \, a_i-a_j\, = 2\leq\, x_i-x_j\, 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 a_0 such that for all 1\leq j\leq k one has \, a_0-a_j\, \leq \, x_0-x_j\, , so that also r_k\leq 1+\, a_0-a_j\, \leq 1+\, x_0-x_j\, \leq r. 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 ...
r \geq 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 if and only if r\geq 1+\sqrt. For instance, the unit balls centered at \sqrte_j, where \_j is an orthonormal basis, are disjoint and included in a ball of radius 1 + \sqrt centered at the origin. Moreover, for r < 1 + \sqrt, the maximum number of disjoint open unit balls inside a ball of radius is \big\lfloor \frac\big\rfloor.


Spheres in a cuboid

Determine the number of spherical objects of given diameter that can be packed into a cuboid of size a \times b \times c.


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 L = 2 + 2/d_n. 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 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 polyominoes 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 *
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 Packing

API for 3D bin packing

3D Boxes and Cylinders packing with telescoping
Many puzzle books as well as mathematical journals contain articles on packing problems.






www.packomania.com
A 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