Circle packing

Last updated
The most efficient way to pack different-sized circles together is not obvious. Citrus fruits.jpg
The most efficient way to pack different-sized circles together is not obvious.

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 density, η, of an arrangement is the proportion of the surface covered by the circles. Generalisations can be made to higher dimensions this is called sphere packing, which usually deals only with identical spheres.

Contents

The branch of mathematics generally known as "circle packing" is concerned with the geometry and combinatorics of packings of arbitrarily-sized circles: these give rise to discrete analogs of conformal mapping, Riemann surfaces and the like.

Densest packing

Identical circles in a hexagonal packing arrangement, the densest packing possible. Circle packing (hexagonal).svg
Identical circles in a hexagonal packing arrangement, the densest packing possible.
Hexagonal packing through natural arrangement of equal circles with transitions to an irregular arrangement of unequal circles. Order and Chaos.tif
Hexagonal packing through natural arrangement of equal circles with transitions to an irregular arrangement of unequal circles.

In the two-dimensional Euclidean plane, Joseph Louis Lagrange proved in 1773 that the highest-density lattice packing of circles is the hexagonal packing arrangement, [1] in which the centres of the circles are arranged in a hexagonal lattice (staggered rows, like a honeycomb), and each circle is surrounded by 6 other circles. For circles of diameter and hexagons of side length , the hexagon area is and the area covered within each hexagon by circles is , allowing the density to be calculated as

Axel Thue published a proof that this same density is optimal among all packings, not just lattice packings, in 1890, but his proof was considered by some to be incomplete. The first rigorous proof is attributed to László Fejes Tóth in 1940. [1] [2]

While the circle has a relatively low maximum packing density, it does not have the lowest possible, even among centrally-symmetric convex shapes: the smoothed octagon has a packing density of about 0.902414, the smallest known for centrally-symmetric convex shapes and conjectured to be the smallest possible. [3] (Packing densities of concave shapes such as star polygons can be arbitrarily small.)

Other packings

At the other extreme, Böröczky demonstrated that arbitrarily low density arrangements of rigidly packed circles exist. [4] [5]

There are 11 circle packings based on the 11 uniform tilings of the plane.[7] In these packings, every circle can be mapped to every other circle by reflections and rotations. The hexagonal gaps can be filled by one circle and the dodecagonal gaps can be filled with 7 circles, creating 3-uniform packings. The truncated trihexagonal tiling with both types of gaps can be filled as a 4-uniform packing. The snub hexagonal tiling has two mirror-image forms.

Fundamental Circle Packings (Better).png

On the sphere

A related problem is to determine the lowest-energy arrangement of identically interacting points that are constrained to lie within a given surface. The Thomson problem deals with the lowest energy distribution of identical electric charges on the surface of a sphere. The Tammes problem is a generalisation of this, dealing with maximising the minimum distance between circles on sphere. This is analogous to distributing non-point charges on a sphere.

In bounded areas

Fifteen equal circles packed within the smallest possible square. Only four equilateral triangles are formed by adjacent circles. Circles packed in square 15.svg
Fifteen equal circles packed within the smallest possible square. Only four equilateral triangles are formed by adjacent circles.

Packing circles in simple bounded shapes is a common type of problem in recreational mathematics. The influence of the container walls is important, and hexagonal packing is generally not optimal for small numbers of circles. Specific problems of this type that have been studied include:

See the linked articles for details.

Unequal circles

A compact binary circle packing with the most similarly sized circles possible. It is also the densest possible packing of discs with this size ratio (ratio of 0.6375559772 with packing fraction (area density) of 0.910683). 2-d dense packing r1.svg
A compact binary circle packing with the most similarly sized circles possible. It is also the densest possible packing of discs with this size ratio (ratio of 0.6375559772 with packing fraction (area density) of 0.910683).

There are also a range of problems which permit the sizes of the circles to be non-uniform. One such extension is to find the maximum possible density of a system with two specific sizes of circle (a binary system). Only nine particular radius ratios permit compact packing, which is when every pair of circles in contact is in mutual contact with two other circles (when line segments are drawn from contacting circle-center to circle-center, they triangulate the surface). [6] For all these radius ratios a compact packing is known that achieves the maximum possible packing fraction (above that of uniformly-sized discs) for mixtures of discs with that radius ratio. [8] All nine have ratio-specific packings denser than the uniform hexagonal packing, as do some radius ratios without compact packings. [9]

It is also known that if the radius ratio is above 0.742, a binary mixture cannot pack better than uniformly-sized discs. [7] Upper bounds for the density that can be obtained in such binary packings at smaller ratios have also been obtained. [10]

Applications

Quadrature amplitude modulation is based on packing circles into circles within a phase-amplitude space. A modem transmits data as a series of points in a 2-dimensional phase-amplitude plane. The spacing between the points determines the noise tolerance of the transmission, while the circumscribing circle diameter determines the transmitter power required. Performance is maximized when the constellation of code points are at the centres of an efficient circle packing. In practice, suboptimal rectangular packings are often used to simplify decoding.

Circle packing has become an essential tool in origami design, as each appendage on an origami figure requires a circle of paper. [11] Robert J. Lang has used the mathematics of circle packing to develop computer programs that aid in the design of complex origami figures.

See also

Related Research Articles

Sphere geometrical object that is the surface of a ball

A sphere is a geometrical object in three-dimensional space that is the surface of a ball.

Truncated icosahedron

In geometry, the truncated icosahedron is an Archimedean solid, one of 13 convex isogonal nonprismatic solids whose 32 faces are two or more types of regular polygons.

Hexagon Shape with six sides

In geometry, a hexagon is a six-sided polygon or 6-gon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°.

Packing problems

Packing problems are a class of optimization problems in 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, 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.

Unit disk

In mathematics, the open unit disk around P, is the set of points whose distance from P is less than 1:

In geometry, inversive geometry is the study of inversion, a transformation of the Euclidean plane that maps circles or lines to other circles or lines and that preserves the angles between crossing curves. Many difficult problems in geometry become much more tractable when an inversion is applied.

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 space has a greater average density than that of the cubic close packing and hexagonal close packing arrangements. The density of these arrangements is around 74.05%.

Sphere packing

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, spaces of other dimensions or to non-Euclidean spaces such as hyperbolic space.

Discrete geometry Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

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 in a given space, a kissing number can also be defined for each individual sphere as the number of spheres it touches. For a lattice packing the kissing number is the same for every sphere, but for an arbitrary sphere packing the kissing number may vary from one sphere to another.

Cone Geometric shape

A cone is a three-dimensional geometric shape that tapers smoothly from a flat base to a point called the apex or vertex.

Close-packing of equal spheres

In geometry, close-packing of equal spheres is a dense arrangement of congruent spheres in an infinite, regular arrangement. Carl Friedrich Gauss proved that the highest average density – that is, the greatest fraction of space occupied by spheres – that can be achieved by a lattice packing is

Snub disphenoid

In geometry, the snub disphenoid, Siamese dodecahedron, triangular dodecahedron, trigonal dodecahedron, or dodecadeltahedron is a three-dimensional convex polyhedron with twelve equilateral triangles as its faces. It is not a regular polyhedron because some vertices have four faces and others have five. It is a dodecahedron, one of the eight deltahedra and one of the 92 Johnson solids. It can be thought of as a square antiprism where both squares are replaced with two equilateral triangles.

In mathematics, a fundamental polygon can be defined for every compact Riemann surface of genus greater than 0. It encodes not only the topology of the surface through its fundamental group but also determines the Riemann surface up to conformal equivalence. By the uniformization theorem, every compact Riemann surface has simply connected universal covering surface given by exactly one of the following:

László Fejes Tóth was a Hungarian mathematician who specialized in geometry. He proved that a lattice pattern is the most efficient way to pack centrally symmetric convex sets on the Euclidean plane. He also investigated the sphere packing problem. He was the first to show, in 1953, that proof of the Kepler conjecture can be reduced to a finite case analysis and, later, that the problem might be solved using a computer.

In geometry, Jung's theorem is an inequality between the diameter of a set of points in any Euclidean space and the radius of the minimum enclosing ball of that set. It is named after Heinrich Jung, who first studied this inequality in 1901. Algorithms also exist to solve the smallest-circle problem explicitly.

Circle packing theorem Describes the possible tangency relations between circles with disjoint interiors

The circle packing theorem describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:

Napkin ring problem

In geometry, the napkin-ring problem involves finding the volume of a "band" of specified height around a sphere, i.e. the part that remains after a hole in the shape of a circular cylinder is drilled through the center of the sphere. It is a counterintuitive fact that this volume does not depend on the original sphere's radius but only on the resulting band's height.

Doyle spiral

In the mathematics of circle packing, a Doyle spiral is a pattern of non-crossing circles in the plane, each tangent to six others. The sequences of circles linked to each other through opposite points of tangency lie on logarithmic spirals having, in general, three different shapes of spirals.

References

  1. 1 2 Chang, Hai-Chau; Wang, Lih-Chung (2010). "A Simple Proof of Thue's Theorem on Circle Packing". arXiv: 1009.4322 [math.MG].
  2. Tóth, László Fejes (1940). "Über die dichteste Kugellagerung". Math. Z. 48: 676–684.
  3. Weisstein, Eric W. "Smoothed Octagon". MathWorld .
  4. Böröczky, K. (1964). "Über stabile Kreis- und Kugelsysteme". Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica. 7: 79–82.
  5. Kahle, Matthew (2012). "Sparse locally-jammed disk packings". Annals of Combinatorics. 16 (4): 773–780. doi:10.1007/s00026-012-0159-0.
  6. 1 2 Tom Kennedy (2006). "Compact packings of the plane with two sizes of discs". Discrete and Computational Geometry. 35 (2): 255–267. arXiv: math/0407145 . doi:10.1007/s00454-005-1172-4.
  7. 1 2 Heppes, Aladár (1 August 2003). "Some Densest Two-Size Disc Packings in the Plane". Discrete and Computational Geometry. 30 (2): 241–262. doi: 10.1007/s00454-003-0007-6 .
  8. Bédaride, Nicolas; Fernique, Thomas (17 February 2020). "Density of Binary Compact Disc Packings". arXiv: 2002.07168 .Cite journal requires |journal= (help)
  9. Kennedy, Tom (2004-07-21). "Circle Packings" . Retrieved 2018-10-11.
  10. de Laat, David; de Oliveira Filho, Fernando Mario; Vallentin, Frank (12 June 2012). "Upper bounds for packings of spheres of several radii". Forum of Mathematics, Sigma. 2. arXiv: 1206.2608 . doi:10.1017/fms.2014.24.
  11. TED.com lecture on modern origami "Robert Lang on TED."

Bibliography