Part of a series on
Puzzles
Types Guessing Riddle Situation Logic Dissection Induction Logic grid Self-reference Mechanical Combination Disentanglement Lock Go problems Folding Stick Tiling Tour Sliding Chess Maze (Logic maze) Word andNumber Crossword Sudoku Puzzle video games Mazes Metapuzzles
Topics Brain teaser Dilemma Joke Optical illusion Packing problems Paradox Problem solving Puzzlehunt Syllogism Tale
Lists Impossible puzzles Maze video games Nikoli puzzle types Puzzle video games Puzzle topics
v t e

Packing problems are a class ofoptimization problems inmathematics that involve attempting to pack objects together into containers. The goal is to either pack a single container asdensely as possible or pack all objects using as few containers as possible. Many of these problems can be related to real-lifepackaging, storage and transportation issues. Each packing problem has a dualcovering 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 abin packing problem, people are given:

• Acontainer, usually a two- or three-dimensionalconvex region, possibly of infinite size. Multiple containers may be given depending on the problem.
• A set ofobjects, 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 maximalpacking density. More commonly, the aim is to pack all the objects into as few containers as possible.^[1] In some variants the overlapping (of objects with each other and/or with the boundary of the container) is allowed but should be minimized.

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 infiniteEuclidean space. This problem is relevant to a number of scientific disciplines, and has received significant attention. TheKepler conjecture postulated an optimal solution forpacking spheres hundreds of years before it wasproven correct byThomas Callister Hales. Many other shapes have received attention, including ellipsoids,^[2]Platonic andArchimedean solids^[3] includingtetrahedra,^[4][5]tripods (unions ofcubes along three positive axis-parallel rays),^[6] and unequal-sphere dimers.^[7]

These problems are mathematically distinct from the ideas in thecircle packing theorem. The relatedcircle packing problem deals with packingcircles, possibly of different sizes, on a surface, for instance theplane or asphere.

Thecounterparts of a circle in other dimensions can never be packed with complete efficiency indimensions 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.^[8]

In three dimensions,close-packed structures offer the bestlattice 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.^[9] The 8-dimensionalE8 lattice and 24-dimensionalLeech lattice have also been proven to be optimal in their respective real dimensional space.

Cubes can easily be arranged to fill three-dimensional space completely, the most natural packing being thecubic honeycomb. No otherPlatonic solid 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 regulardodecahedra is based on the aforementioned face-centered cubic (FCC) lattice.

Tetrahedra andoctahedra together can fill all of space in an arrangement known as thetetrahedral-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.^[3]

Determine the minimum number ofcuboid 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.

The problem of finding the smallest ball such thatkdisjoint openunit balls may be packed inside it has a simple and complete answer inn-dimensional Euclidean space if${\displaystyle k\le n+1}$, and in an infinite-dimensionalHilbert space with no restrictions. It is worth describing in detail here, to give a flavor of the general problem. In this case, a configuration ofk pairwisetangent unit balls is available. People place the centers at the vertices${\displaystyle a_1,\dots ,a_k}$ of a regular${\displaystyle (k-1)}$ dimensionalsimplex with edge 2; this is easily realized starting from anorthonormal 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 fromat least one of thek vertices. In terms of inclusions of balls, thek 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 ofk disjoint open unit balls contained in a ball of radiusr centered at a point${\displaystyle x_0}$. Consider themap 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 \Vert a_i-a_j\Vert =2\le \Vert x_i-x_j\Vert }$ this map is 1-Lipschitz and by theKirszbraun 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 arek disjoint unit open balls in a ball of radiusrif 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 radiusr 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, the maximum number of disjoint open unit balls inside a ball of radiusr is$${\displaystyle \lfloor \frac{2}{2-(r-1{)}^2}\rfloor .}$$

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

People determine the minimum heighth of acylinder with given radiusR that will packn identical spheres of radiusr (<R).^[12] For a small radiusR the spheres arrange to ordered structures, calledcolumnar structures.

People determine the minimum radiusR that will packn identical, unitvolumepolyhedra of a given shape.^[13]

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

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

• Packing circles in acircle - 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 forn ≤ 14, andn = 19.
• Packing circles in asquare - 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 forn ≤ 30.
• Packing circles in arectangle
• Packing circles in anisosceles right triangle - good estimates are known forn < 300.
• Packing circles in anequilateral triangle - Optimal solutions are known forn ≤ 15, andconjectures are available forn ≤ 34.^[14]

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

• Packing squares in asquare: Optimal solutions have been proven forn from 1-10, 14-16, 22-25, 33-36, 62-64, 79-81, 98-100, and anysquareinteger. The wasted space is asymptoticallyO(a^3/5).
• Packing squares in acircle: Good solutions are known forn ≤ 35.

  

• Packing identical rectangles in a rectangle: The problem of packing multiple instances of a singlerectangle 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 minimumarea (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 isNP-complete in general, but there are fast algorithms for solving small instances.

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

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

Ana ×b rectangle can be packed with 1 ×n strips if and only ifn dividesa orn dividesb.^[15][16]

de Bruijn's theorem: A box can be packed with aharmonic bricka ×a b ×a b c if the box has dimensionsa p ×a b q ×a b c r for somenatural numbersp,q,r (i.e., the box is a multiple of the brick.)^[15]

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

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

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.^[17]

The problem of deciding whether a given set ofpolygons can fit in a given square container has been shown to be complete for theexistential theory of the reals.^[18]

• Bin packing problem
• Close-packing of equal spheres
• Conway puzzle
• Covering problem
• Cutting stock problem
• Ellipsoid packing
• Kissing number problem
• Knapsack problem
• Random close pack
• Set packing
• Slothouber–Graatsma puzzle
• Strip packing problem
• Tetrahedron packing
• Tetris

• Weisstein, Eric W."Klarner's Theorem".MathWorld.
• Weisstein, Eric W."de Bruijn's Theorem".MathWorld.

Wikimedia Commons has media related toPacking problems.

• Optimizing Three-Dimensional Bin Packing

Many puzzle books as well as mathematical journals contain articles on packing problems.

• Links to various MathWorld articles on packing
• MathWorld notes on packing squares.
• Erich's Packing Center
• www.packomania.com A site with tables, graphs, calculators, references, etc.
• "Box Packing" byEd Pegg, Jr., theWolfram Demonstrations Project, 2007.
• Best known packings of equal circles in a circle, up to 1100

• Circle packing challenge problem in Python

• Packing problems

• Articles with short description
• Short description is different from Wikidata
• Commons category link from Wikidata
• Use dmy dates from September 2019