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.

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

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, in which the centres of the circles are arranged in a hexagonal lattice (staggered rows, like a honeycomb), and each circle is surrounded by six other circles. For circles of diameter  and hexagons of side length , the hexagon area and the circle area are, respectively:

The area covered within each hexagon by circles is:

Finally, the packing density is:

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

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. (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.

There are eleven circle packings based on the eleven uniform tilings of the plane. 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 seven 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.

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

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:
Circle packing in a circle
Circle packing in a square
Circle packing in a rectangle
Circle packing in an equilateral triangle
Circle packing in an isosceles right triangle
See the linked articles for details.

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). 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. All nine have ratio-specific packings denser than the uniform hexagonal packing, as do some radius ratios without compact packings.

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

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 two-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.  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 rectangle
Circle packing in a square
Circle packing in a circle
Inversive distance
Kepler conjecture
Malfatti circles
Packing problem

References

Bibliography
기하학에서 원 채우기는 (크기가 동일하거나 다양한) 주어진 표면에서 겁침이 일어나지 않고 모든 원이 서로 접촉하도록 하는 원의 배열에 관한 연구이다. 배열의 관련 채우기 밀도 η는 표면에서 원이 차지하고 있는 비율이다. 높은 차원으로 일반화도 가능하다 - 이것 중 동일한 구만 다루는 문제는 구 채우기라고 부른다.

원은 유클리드 평면에서 0.9069의 상대적으로 낮은 최대 채우기 밀도를 가지지만, 가능한 최소 밀도는 아니다. 평면에서 "최악"의 채우기 모양은 알려지지 않았지만, 매끄러운 팔각형은 채우기 밀도가 0.902414로 원점대칭인 볼록한 도형 중에서 채우기 밀도가 가장 낮다.
다각형 별과 같은 오목한 다각형의 채우기 밀도는 임의적으로 작을 수 있다.

일반적으로 원 채우기라고 알려진 수학 분야는 임의의 크기의 원의 채우기의 기하학과 조합과 관련이 있다: 이 때문에 등각 사상, 리만 곡면 등의 이산 해석을 준다.

평면에 채우기 

2차원 유클리드 공간에서, 조제프루이 라그랑주는 1773년에 원의 가장 조밀한 배열 격자는 육각형 채우기 배열이라는 것을 증명했다. 육각형 채우기 배열은 원의 중심이 육각형 격자(벌집과 같이 열이 늘어져 있다)에 놓여 있고, 각 원은 6개의 원에 둘러 싸여 있다. 배열의 밀도는
 
1890년에 악셀 투에는 원의 크기가 균일할 때와 균일하지 않을 때에 모든 가능한 채우기 중에서 육각 격자가 가장 밀도가 높다는 것을 보임으로 이것이 최적이라는 것을 처음으로 증명하였다.하지만 그의 증명은 불완정하다.  엄밀한 증명은 1940년에 라즐로 피에스 토스(László Fejes Tóth)가 처음으로 제시하였다.

다른 극단에서 Böröczky는 엄격하게 채워진 원의 임의의 낮은 밀도 배열이 존재함을 증명하였다.

균등 채우기 
11개의 평면에서의 균등 타일링을 기반으로 한 11개의 원 채우기가 있다. I이 채우기에서 모든 원은 대칭과 회전으로 다른 모든 원들과 매핑된다. 육각형의 틈은 원 하나로 채워지고 십이각형 틈은 3-균등 채우기를 만들면서 7개의 원으로 채워진다. 두 종류의 틈을 가진 잘린 삼육각형 타일링은 4-균등 채우기로 채울 수 있다. 다듬은 육각형 타일링은  거울상 두 개 가지고 있다.

구에서 채우기 
관련 문제는 주어진 표면 위에서 움직이고 동일하게 간섭하는 점들치 최소 에너지를 갖게 하는 배열을 결정하는 것이다. 톰슨 문제는 구 표면에서 동일한 전하들의 가장 에너지가 작은 분포를 다룬다. 타메스 문제는 이것의 일반화로 구에서 원의 최소거리를 최대화하는 문제를 다룬다. 이것은 구에서 점전하가 아닌 것을 배열과 유사하다.

제한된 영역에서 채우기 

간단한 경계를 가진 도형 안에서 원 채우기는 유희 수학의 일반적인 종류의 문제이다. 용기의 벽의 영양은 중요하고 육각형 채우기는 원이 적을 때는 최적이 아니다.

동일하지 않은 원 

또한 원의 크기가 동일하지 않은 문제도 존재한다.  O이러한 확장은 특정한 두 원의 크기의 시스템(이진 시스템)의 최대 밀도를 찾는 것이다.  O오직 9가지의 반지름 비율이 콤팩트 채우기를 가능하게 한다. 콤팩트 채우기는 모든 원의 쌍이 다른 두 원과 접촉하는 채우기이다(접촉한 원의 중심을 이은 선분을 그리면 표면이 삼각형으로 가득차게 된다). 이 반지름 비가 7일 때 콤팩트 채우기는 (위에서 균일한 크기의 원에 나온)최대 채우기 밀도에 도달하는 채우기가 알려져 있다. 가장 높은 채우기 밀도는 0.911627478 이고, 이 때의 반지름 비는 0.545151042이다·

반지름 비가 0.742이상일 때, 이진 혼합물은 균일한 크기의 원의 채우기보다 좋게 채울 수 없다는 것은 알려져 있다. 이보다 작은 밀도의 이진 채우기의 밀도의 상한도 역시 얻어졌다.

원 채우기의 적용 
직교 진폭 변조는 위상-진폭 공간의 원에 원 채우기에 기반한다. 모뎀은 데이터를 2차원 위상-진폭 공간에서 일련의 점으로 전송한다. 두 점 사이의 거리는 전송기의 노이즈의 허용치를 결정하지만 외접하는 원의 지름은 전송기 전력 요구량을 결정한다. 코드 점의 배치가 효율적인 원 채우기의 중심에 있을 때 효율이 최대화 된다. 실제로 디코딩을 단순화 하기 위해서 차선인 직사각형 채우기가 사용된다.

원 채우기는 종이접기 디자인에서도 중요하다. 종이접기의 각 부분은 종이의 원이 필요하다. 로버트 J. 랭은 원 채우기의 수학을 사용해서 복잡한 종이접기 디자인을 돕기 위한 컴퓨터 프로그램을 만들었다.

같이 보기 

 아폴로니안 개스킷
 정사각형 안에 원 채우기
 원 안에 원 채우기
 뒤집힌 거리
 케플러의 추측
 말파티 원
 채우기 문제

참고 문헌

각주 

원 채우기