Circle packing: Difference between revisions
No edit summary |
→Packings in the plane: Adding note about Carl Friedrich Gauss's finding in 1831 with regard to hexagonal packing of equal circles |
||
Line 17: | Line 17: | ||
::<math>\eta_h = \frac{\pi\sqrt{3}}{6} \approx 0.9069.</math> |
::<math>\eta_h = \frac{\pi\sqrt{3}}{6} \approx 0.9069.</math> |
||
[[Axel Thue]] provided the first proof that this was optimal in 1890, showing that the hexagonal lattice is the densest of all possible circle packings, both regular and irregular. However, his proof was considered by some to be incomplete. The first rigorous proof is attributed to [[László Fejes Tóth]] in 1940.<ref name="ChangWang">{{cite arXiv |last1=Chang |first1=Hai-Chau |last2=Wang |first2=Lih-Chung |eprint=1009.4322 |title=A Simple Proof of Thue's Theorem on Circle Packing |class=math.MG |date=2010 }}</ref><ref name="Toth">{{cite journal|first=László Fejes|last=Tóth|title=Über die dichteste Kugellagerung|journal=Math. Z. |date=1940|volume=48|pages=676–684}}</ref> |
Hexagonal packing of equal circles was found to fill a fraction Pi/Sqrt[12] ≃ 0.91 of area—which was proved maximal for periodic packings by [[Carl Friedrich Gauss]] in 1831.<ref>{{cite book|last=Wolfram|first=Stephen|title=A New Kind of Science|publisher=Wolfram Media, Inc.|year=2002|page=985|isbn=1-57955-008-8}}</ref> Later, [[Axel Thue]] provided the first proof that this was optimal in 1890, showing that the hexagonal lattice is the densest of all possible circle packings, both regular and irregular. However, his proof was considered by some to be incomplete. The first rigorous proof is attributed to [[László Fejes Tóth]] in 1940.<ref name="ChangWang">{{cite arXiv |last1=Chang |first1=Hai-Chau |last2=Wang |first2=Lih-Chung |eprint=1009.4322 |title=A Simple Proof of Thue's Theorem on Circle Packing |class=math.MG |date=2010 }}</ref><ref name="Toth">{{cite journal|first=László Fejes|last=Tóth|title=Über die dichteste Kugellagerung|journal=Math. Z. |date=1940|volume=48|pages=676–684}}</ref> |
||
At the other extreme, Böröczky demonstrated that arbitrarily low density arrangements of rigidly packed circles exist.<ref>{{cite journal|last1=Böröczky|first1=K.|title=Über stabile Kreis- und Kugelsysteme|journal=Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica|date=1964|volume=7|pages=79–82}}</ref><ref>{{cite journal|last1=Kahle|first1=Matthew|title=Sparse locally-jammed disk packings|journal=Annals of Combinatorics|date=2012|volume=16|issue=4|pages=773–780|doi=10.1007/s00026-012-0159-0}}</ref> |
At the other extreme, Böröczky demonstrated that arbitrarily low density arrangements of rigidly packed circles exist.<ref>{{cite journal|last1=Böröczky|first1=K.|title=Über stabile Kreis- und Kugelsysteme|journal=Annales Universitatis Scientiarum Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica|date=1964|volume=7|pages=79–82}}</ref><ref>{{cite journal|last1=Kahle|first1=Matthew|title=Sparse locally-jammed disk packings|journal=Annals of Combinatorics|date=2012|volume=16|issue=4|pages=773–780|doi=10.1007/s00026-012-0159-0}}</ref> |
Revision as of 17:20, 6 March 2019
- This article describes the packing of circles on surfaces. For the related article on circle packing with a prescribed intersection graph, please see the circle packing theorem.
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 all circles touch one another. 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.
While the circle has a relatively low maximum packing density of 0.9069 on the Euclidean plane, it does not have the lowest possible. The "worst" shape to pack onto a plane is not known, but the smoothed octagon has a packing density of about 0.902414, which is the lowest maximum packing density known of any centrally-symmetric convex shape.[1] Packing densities of concave shapes such as star polygons can be arbitrarily small.
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
Packings in the plane
In two dimensional Euclidean space,
Hexagonal packing of equal circles was found to fill a fraction Pi/Sqrt[12] ≃ 0.91 of area—which was proved maximal for periodic packings by Carl Friedrich Gauss in 1831.[3] Later, Axel Thue provided the first proof that this was optimal in 1890, showing that the hexagonal lattice is the densest of all possible circle packings, both regular and irregular. However, his proof was considered by some to be incomplete. The first rigorous proof is attributed to László Fejes Tóth in 1940.[2][4]
At the other extreme, Böröczky demonstrated that arbitrarily low density arrangements of rigidly packed circles exist.[5][6]
Uniform packings
There are 11 circle packings based on the 11
Triangular |
Square |
Hexagonal |
Elongated triangular |
Trihexagonal |
Snub square |
Truncated square |
Truncated hexagonal |
Rhombitrihexagonal |
Snub hexagonal
|
Snub hexagonal (mirrored) |
Truncated trihexagonal |
Packings 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.
Packings in bounded areas
Unequal circles
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).[8] For seven of 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. All nine have ratio-specific packings denser than the uniform triangular packing, as do some radius ratios without compact packings[10]
It is also known that if the radius ratio is above 0.742, a binary mixture cannot pack better than uniformly-sized discs.[9] Upper bounds for the density that can be obtained in such binary packings at smaller ratios have also been obtained.[11]
Applications of circle packing
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.[12] 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
- Apollonian gasket
- Circle packing in a square
- Circle packing in a circle
- Inversive distance
- Kepler conjecture
- Malfatti circles
- Packing problem
Bibliography
- Wells D (1991). The Penguin Dictionary of Curious and Interesting Geometry. New York: Penguin Books. pp. 30–31, 167. ISBN 0-14-011813-6.
- Stephenson, Kenneth (December 2003). "Circle Packing: A Mathematical Tale" (PDF). Notices of the American Mathematical Society. 50 (11).
References
- ^ Weisstein, Eric W. "Smoothed Octagon". MathWorld.
- ^ ].
- ISBN 1-57955-008-8.
- ^ Tóth, László Fejes (1940). "Über die dichteste Kugellagerung". Math. Z. 48: 676–684.
- ^ 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.
- .
- ISBN 0-486-23729-X.
- ^ .
- ^ .
- ^ Kennedy, Tom (2004-07-21). "Circle Packings". Retrieved 2018-10-11.
- .
- ^ TED.com lecture on modern origami "Robert Lang on TED."