In geometry, a sphere packing is an arrangement of non-overlapping spheres
within a containing space. The spheres considered are usually all of identical
size, and the space is usually three-dimensional Euclidean space.
However, sphere packing problems can be generalised to consider unequal spheres,
n-dimensional Euclidean space or to non-Euclidean spaces such as hyperbolic
space. A typical sphere packing problem is to
find an arrangement in which the spheres fill as large a proportion of the space
as possible. The proportion of space filled by the spheres is called the
density of the arrangement. As the local density of a packing in an infinite
space can vary depending on the volume over which it is measured, the problem
is usually to maximise the average or asymptotic density, measured over a
large enough volume. For equal spheres the densest packing
uses approximately 74% of the volume. Random packing of equal spheres
generally have a density around 64%. Classification and terminology
A lattice arrangement is one in which the centers of the spheres form a very
symmetric pattern which only needs n vectors to be uniquely defined. Lattice
arrangements are periodic. Arrangements in which the spheres do not form a
lattice can still be periodic, but also aperiodic or random. Lattice
arrangements are easier to handle than irregular ones—their high degree of
symmetry makes it easier to classify them and to measure their densities.
Regular packing = Dense packing =
In three-dimensional Euclidean space, the densest packing of equal spheres is
achieved by a family of structures called close-packed structures. One
method for generating such a structure is as follows. Consider a plane with a
compact arrangement of spheres on it. For any three neighbouring spheres, a
fourth sphere can be placed on top in the hollow between the three bottom
spheres. If we do this "everywhere" in a second plane above the first, we create
a new compact layer. A third layer can be placed directly above the first one,
or the spheres can be offset, vertically above another set of hollows of the
first layer. There are thus three types of planes, called A, B and C.
Two simple arrangements within the close-packed family correspond to
regular lattices. One is called cubic close packing — where the layers are
alternated in the ABCABC… sequence. The other is called hexagonal close packing
— where the layers are alternated in the ABAB… sequence. But many layer stacking
sequences are possible, and still generate a close-packed structure. In
all of these arrangements each sphere is surrounded by 12 other spheres, and the
average density is Gauss proved in 1831 that these packings
have the highest density amongst all possible lattice packings.
In 1611 Johannes Kepler had conjectured that this is the maximum possible
density amongst both regular and irregular arrangements — this became
known as the Kepler conjecture. In 1998, Thomas Callister Hales, following the
approach suggested by László Fejes Tóth in 1953, announced a proof of the Kepler
conjecture. Hales' proof is a proof by exhaustion involving checking of many
individual cases using complex computer calculations. Referees said that they
were "99% certain" of the correctness of Hales' proof. On 10 August 2014 Hales
announced the completion of a formal proof using automated proof checking,
removing any doubt. = Other common lattice packings =
Some other lattice packings are often found in physical systems. These include
the cubic lattice with a density of , the hexagonal lattice with a density of
, and the tetrahedral lattice with a density of and loosest possible at a
density of 0.0555. = Jammed packings with a low density =
Packings where all spheres are constrained by their neighbours to stay
in one location are called rigid or jammed. The strictly jammed sphere
packing with the lowest density is a diluted fcc crystal with a density of
only 0.49365. Irregular packing
If we attempt to build a densely packed collection of spheres we will be tempted
to always place the next sphere in a hollow between three packed spheres. If
five spheres are assembled in this way, they will be consistent with one of the
regularly packed arrangements described above. However, the sixth sphere placed
in this way will render the structure inconsistent with any regular
arrangement. This results in the possibility of a random close packing of
spheres which is stable against compression.
When spheres are randomly added to a container and then compressed, they will
generally form what is known as an "irregular" or "jammed" packing
configuration when they can be compressed no more. This irregular
packing will generally have a density of about 64%. Recent research predicts
analytically that it cannot exceed a density limit of 63.4% This situation is
unlike the case of one or two dimensions, where compressing a
collection of 1-dimensional or 2-dimensional spheres will yield a
regular packing. Hypersphere packing
The sphere packing problem is the three-dimensional version of a class of
ball-packing problems in arbitrary dimensions. In two dimensions, the
equivalent problem is packing circles on a plane.
In dimensions higher than three, the densest regular packings of hyperspheres
are known up to 8 dimensions. Very little is known about irregular
hypersphere packings; it is possible that in some dimensions the densest
packing may be irregular. Some support for this conjecture comes from the fact
that in certain dimensions the densest known irregular packing is denser than
the densest known regular packing. Dimension 24 is special due to the
existence of the Leech lattice, which has the best kissing number and is the
densest lattice packing. No better irregular packing is known, and an
irregular packing could, at best, improve over the Leech lattice packing
by a factor of less than 1+2×10−30. Another line of research in high
dimensions is trying to find asymptotic bounds for the density of the densest
packings. Currently the best known result is that there exists a lattice in
dimension n with density bigger or equal to for some number c.
Unequal sphere packing Many problems in the chemical and
physical sciences can be related to packing problems where more than one
size of sphere is available. Here there is a choice between separating the
spheres into regions of close-packed equal spheres, or combining the multiple
sizes of spheres into a compound or interstitial packing. When many sizes of
spheres are available, the problem quickly becomes intractable, but some
studies of binary hard spheres are available.
When the second sphere is much smaller than the first, it is possible to
arrange the large spheres in a close-packed arrangement, and then
arrange the small spheres within the octahedral and tetrahedral gaps. The
density of this interstitial packing depends sensitively on the radius ratio,
but in the limit of extreme size ratios, the smaller spheres can fill the gaps
with the same density as the larger spheres filled space. Even if the large
spheres are not in a close-packed arrangement, it is always possible to
insert some smaller spheres of up to 0.29099 of the radius of the larger
sphere. When the smaller sphere has a radius
greater than 0.41421 of the radius of the larger sphere, it is no longer
possible to fit into even the octahedral holes of the close-packed structure.
Thus, beyond this point, either the host structure must expand to accommodate the
interstitials, or rearrange into a more complex crystalline compound structure.
Structures are known which exceed the close packing density for radius ratios
up to 0.659786. Upper bounds for the density that can be
obtained in such binary packings have also been obtained.
In many chemical situations such as ionic crystals, the stoichiometry is
constrained by the charges of the constituent ions. This additional
constraint on the packing, together with the need to minimize the Coulomb energy
of interacting charges leads to a diversity of optimal packing
arrangements. Hyperbolic space
Although the concept of circles and spheres can be extended to hyperbolic
space, finding the densest packing becomes much more difficult. In a
hyperbolic space there is no limit to the number of spheres that can surround
another sphere. The concept of average density also becomes much more difficult
to define accurately. The densest packings in any hyperbolic space are
almost always irregular. Despite this difficulty, K. Böröczky
gives a universal upper bound for the density of sphere packings of hyperbolic
n-space where . In three dimensions the Böröczky bound is approximately
85.327613%, and is realized by the horosphere packing of the order-6
tetrahedral honeycomb with Schläfli symbol {3,3,6}. In addition to this
configuration at least three other horosphere packings are known to exist
in hyperbolic 3-space that realize the density upper bound.
Touching pairs, triplets, and quadruples The contact graph of an arbitrary finite
packing of unit balls is the graph whose vertices correspond to the packing
elements and whose two vertices are connected by an edge if the
corresponding two packing elements touch each other. The cardinality of the edge
set of the contact graph gives the number of touching pairs, the number of
3-cycles in the contact graph gives the number of touching triplets, and the
number of tetrahedrons in the contact graph gives the number of touching
quadruples-tuples in the sphere packing). In the case of 3-dimensional
Euclidean space, non-trivial upper bounds on the number of touching pairs,
triplets, and quadruples were proved by Karoly Bezdek and Samuel Reid at the
University of Calgary. Other spaces
Sphere packing on the corners of a hypercube corresponds to designing
error-correcting codes: if the spheres have radius t, then their centers are
codewords of a 2t+1-error-correcting code. Lattice packings correspond to
linear codes. There are other, subtler relationships between Euclidean sphere
packing and error-correcting codes. For example, the binary Golay code is
closely related to the 24-dimensional Leech lattice.
For further details on these connections, see the book of Conway and
Sloane. See also
Close-packing of equal spheres Apollonian sphere packing
Hermite constant Kissing number problem
Sphere-packing bound Random close pack
References Bibliography
Aste T, Weaire D. The Pursuit of Perfect Packing. London: Institute of Physics
Publishing. ISBN 0-7503-0648-3. Conway JH, Sloane NJH. Sphere Packings,
Lattices and Groups. ISBN 0-387-98585-9. Sloane, N. J. A.. "The Packing of
Spheres". Scientific American 250: 116–125. Bibcode:1984SciAm.250..116G.
doi:10.1038/scientificamerican0584-116. External links
Dana Mackenzie "A fine mess" A non-technical overview of packing in
hyperbolic space. Weisstein, Eric W., "Circle Packing",
MathWorld. "Kugelpackungen"
"3D Sphere Packing Applet" Sphere Packing java applet
"Densest Packing of spheres into a sphere" java applet
"Database of sphere packings"