HOME

TheInfoList



OR:

Packing problems are a class of
optimization problem In mathematics, engineering, computer science and economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
s in
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
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 coo ...
, storage and transportation issues. Each packing problem has a dual covering problem, 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 The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has m ...
, people are given: * A ''container'', usually a two- or three-dimensional convex region, 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, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
. 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 The Archimedean solids are a set of thirteen convex polyhedra whose faces are regular polygon and are vertex-transitive, although they aren't face-transitive. The solids were named after Archimedes, although he did not claim credit for them. They ...
s including tetrahedra, tripods (unions of
cube A cube or regular hexahedron is a three-dimensional space, three-dimensional solid object in geometry, which is bounded by six congruent square (geometry), square faces, a type of polyhedron. It has twelve congruent edges and eight vertices. It i ...
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 related circle packing problem deals with packing
circle A circle is a shape consisting of all point (geometry), points in a plane (mathematics), plane that are at a given distance from a given point, the Centre (geometry), centre. The distance between any point of the circle and the centre is cal ...
s, possibly of different sizes, on a surface, for instance the plane or a
sphere A sphere (from Ancient Greek, Greek , ) is a surface (mathematics), surface analogous to the circle, a curve. In solid geometry, a sphere is the Locus (mathematics), set of points that are all at the same distance from a given point in three ...
. 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 coo ...
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 people 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 In mathematics, the Leech lattice is an even unimodular lattice Λ24 in 24-dimensional Euclidean space which is one of the best models for the kissing number problem. It was discovered by . It may also have been discovered (but not published) by Er ...
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 (geometry), honeycomb) in Euclidean 3-space made up of cube, cubic cells. It has 4 cubes around every edge, and 8 cubes around each verte ...
. No other
Platonic solid In geometry, a Platonic solid is a Convex polytope, convex, regular polyhedron in three-dimensional space, three-dimensional Euclidean space. Being a regular polyhedron means that the face (geometry), faces are congruence (geometry), congruent (id ...
can tile space on its own, but some preliminary results are known. Tetrahedra 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. 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 with quadrilateral faces, meaning it is a polyhedron with six Face (geometry), faces; it has eight Vertex (geometry), vertices and twelve Edge (geometry), edges. A ''rectangular cuboid'' (sometimes also calle ...
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: General measurement * Unit of measurement, a definite magnitude of a physical quantity, defined and adopted by convention or by law **International System of Units (SI), modern form of the metric system **English units, histo ...
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, a Hilbert space is a real number, real or complex number, complex inner product space that is also a complete metric space with respect to the metric induced by the inner product. It generalizes the notion of Euclidean space. The ...
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, intuitively, the straight line that "just touches" the curve at that point. Leibniz defined it as the line through a pair of infinitely close points o ...
unit balls is available. People place the centers at the vertices a_1, \dots, a_k of a regular (k-1) dimensional simplex 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 (linear algebra), dimension is a Basis (linear algebra), basis for V whose vectors are orthonormal, that is, they are all unit vec ...
. 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 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" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
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 \left\lfloor \frac\right\rfloor.


Spheres in a cuboid

People 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

People determine the minimum height of a cylinder 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

People determine the minimum radius that will pack identical, unit
volume Volume is a measure of regions in 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 (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...
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
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 a rectangle * 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 or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
s are available for .


Packing of squares

People 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 coordinat ...
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 geometry, a square is a regular polygon, regular quadrilateral. It has four straight sides of equal length and four equal angles. Squares are special cases of rectangles, which have four equal angles, and of rhombuses, which have four equal si ...
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
. 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 geometry, Euclidean plane geometry, a rectangle is a Rectilinear polygon, rectilinear convex polygon or a quadrilateral with four right angles. It can also be defined as: an equiangular quadrilateral, since equiangular means that a ...
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 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 measure of a region's size on a 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 open surface or the boundary of a three-di ...
(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, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
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
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 popu ...
es into a larger rectangle or other square-like shape. There are significant
theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...
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: 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 number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
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 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
polygon In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon ...
s can fit in a given square container has been shown to be complete for the existential theory of the reals..


See also

*
Bin packing problem The bin packing problem is an optimization problem, in which items of different sizes must be packed into a finite number of bins or containers, each of a fixed given capacity, in a way that minimizes the number of bins used. The problem has m ...
* Close-packing of equal spheres * Conway puzzle * Covering problem * Cutting stock problem * Ellipsoid packing * Kissing number problem *
Knapsack problem The knapsack problem is the following problem in combinatorial optimization: :''Given a set of items, each with a weight and a value, determine which items to include in the collection so that the total weight is less than or equal to a given lim ...
* Random close pack * Set packing * Slothouber–Graatsma puzzle * Strip packing problem * Tetrahedron packing * Tetris


Notes


References

* *


External links


Optimizing Three-Dimensional Bin Packing
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., the
Wolfram Demonstrations Project The Wolfram Demonstrations Project is an Open source, open-source collection of Interactive computing, interactive programmes called Demonstrations. It is hosted by Wolfram Research. At its launch, it contained 1300 demonstrations but has grown t ...
, 2007.
Best known packings of equal circles in a circle, up to 1100

Circle packing challenge problem in Python
{{Packing problem