Circle packing

Circle packing concerns the arrangement of non-overlapping circles within a given region, with the goal of maximizing the proportion of the region covered by the circles, known as the packing density. In the infinite plane, the densest arrangement of equal circles is the hexagonal lattice, where each circle touches six others, achieving a density of π/(2√3) ≈ 0.9069.¹ This result was conjectured by Johannes Kepler in 1611 and proved by László Fejes Tóth in 1940, a proof later simplified by others.² The hexagonal packing is also the basis for many practical applications, such as the arrangement of fibers in optical cables and the stacking of spheres in a plane.

When the container is bounded, such as a square or a circle, the problem becomes more complex. For a given number of equal circles, the goal is to find the smallest container that can hold them, or equivalently, to maximize the radius of the circles. These problems are notoriously difficult, with exact solutions known only for small numbers of circles. For example, the optimal packing of 5 circles in a square was proven only in 1968, and many cases remain open.³ Computational methods, such as nonlinear optimization and simulated annealing, are often used to find near-optimal arrangements, and the results are cataloged in online databases like Packomania.⁴ These problems have applications in packaging, pallet loading, and the design of circular containers for cylindrical objects.

Circle packing is not merely a mathematical curiosity; it has practical applications in various fields. In materials science, the packing of equal circles models the arrangement of atoms in a monolayer, influencing properties like surface tension and catalytic activity.⁵ In coding theory, circle packing in high-dimensional spaces is related to error-correcting codes, where the minimum distance between codewords corresponds to the radius of non-overlapping spheres. The problem also appears in logistics, such as optimizing the layout of circular objects in a shipping container, and in the design of wireless sensor networks, where coverage areas are modeled as circles.

Beyond the classic equal-circle problem, there are many niche variations. For instance, packing circles of different sizes, known as unequal circle packing, has no simple optimal solution and is often tackled with heuristics. Another variant is the packing of circles on a sphere, which is relevant to the Thomson problem in physics and the placement of satellites in orbit. A surprising connection exists between circle packing and complex analysis: the Koebe–Andreev–Thurston theorem states that any planar graph can be represented as a circle packing, leading to applications in conformal mapping and the study of hyperbolic geometry.⁶ Additionally, the concept of "circle packing" is used in the design of origami patterns and in the visualization of hierarchical data, such as treemaps.

Packing density

The fraction of the container's area that is covered by the circles.

Hexagonal packing

An arrangement of equal circles in a hexagonal lattice, where each circle touches six others, achieving the maximum density in the plane.

Koebe–Andreev–Thurston theorem

A theorem stating that every planar graph can be represented as a circle packing, with tangencies corresponding to edges.