Fact-checked by Grok 2 weeks ago

Circle packing

Circle packing refers to the arrangement of non-overlapping circles in a plane, sphere, or other geometric container, often with specified tangency patterns or to achieve maximal density.^[1] These configurations can involve equal or varying circle sizes and have been studied since antiquity, with notable examples including the hexagonal lattice packing in the plane, which achieves a density of \pi / \sqrt{12} \approx 0.9069.^[2] The mathematical foundations of circle packing trace back to ancient problems like the Apollonian circle packing, a fractal-like structure generated iteratively from three mutually tangent circles, and early tangency puzzles in Greek and Japanese geometry.^[1] Modern developments began with Koebe's 1936 circle packing theorem, which guarantees a packing of circles corresponding to any planar graph, later generalized by the Koebe–Andreev–Thurston theorem (1970–1980s), stating that for any finite triangulation of the sphere, there exists a unique circle packing in the plane (up to Möbius transformations) where circles are tangent if their vertices are adjacent.^[2] This theorem underpins discrete analogues of complex analysis, such as the discrete Riemann mapping theorem, where circle packings approximate conformal maps and converge to classical Riemann mappings as mesh size decreases.^[1] Circle packings extend to hyperbolic and spherical geometries and serve as tools for uniformization of surfaces, bridging topology, geometry, and analysis.^[2] In optimization contexts, such as packing equal circles into a larger circle, the goal is to maximize density—the ratio of packed area to container area—with optimal configurations known for small numbers (e.g., up to 11 circles) and computational methods like repulsion algorithms yielding near-optimal results for larger sets.^[3] Applications span neuroscience (cortical surface mapping), computer graphics (conformal tilings), and materials science (modeling granular media), with software like CirclePack enabling computations for millions of circles.^[1]

Fundamentals

Definition and Basic Concepts

Circle packing is the arrangement of non-overlapping circles within a plane, on a curved surface, or inside a bounded region, with the objective often being to maximize the packing density or to satisfy specific geometric constraints.^[2] In this context, circles are typically understood as closed disks, consisting of their interior and boundary, and the packings require that the interiors of any two circles be disjoint while allowing their boundaries to touch.^[4] Such arrangements are interior-disjoint, meaning no point lies in the interior of more than one circle, and tangent circles share exactly one boundary point.^[2] A foundational prerequisite from Euclidean geometry is that the distance between the centers of any two circles must be at least the sum of their radii, ensuring non-overlap via the triangle inequality applied to the line segment connecting the centers and the radii as sides of a degenerate triangle.^[5] This condition implies that circles cannot intersect interiors but may touch externally. In the plane, a key limitation is that no three circles can be mutually tangent without forming a cusp-shaped interstitial gap, as the local geometry around a point of tangency restricts configurations; this relates to the kissing number in two dimensions being exactly 6, meaning at most six equal circles can touch a central equal circle without overlapping.^[5] The packing density \rho quantifies the efficiency of an arrangement and is defined as the ratio of the total area covered by the circles to the area of the containing region.^[6] For infinite packings of equal circles in the Euclidean plane, Thue's theorem establishes an upper bound of \rho \leq \frac{\pi}{\sqrt{12}} \approx 0.9069.^[6] A brief proof sketch using Voronoi cells proceeds as follows: Consider the Voronoi diagram of the circle centers, where each cell is the set of points closer to its center than to any other. In a saturated packing (where no additional circle can be inserted without overlap), each Voronoi cell contains exactly one circle and has area at least that of a regular hexagon with inradius equal to the circle's radius r, which is \frac{2\sqrt{3}}{3} r^2 \times 3 = 2\sqrt{3} r^2. Since the circle's area is \pi r^2, the density satisfies \rho \leq \frac{\pi r^2}{2\sqrt{3} r^2} = \frac{\pi}{2\sqrt{3}} = \frac{\pi}{\sqrt{12}}. This bound is tight, as it is achieved in the hexagonal lattice arrangement.^[6]

Historical Development

The study of circle packing traces its origins to ancient Greek geometry, where arrangements of circles featured in problems of tiling and approximation. Archimedes' investigations into sphere stacking in his treatise On the Sphere and Cylinder (c. 250 BCE) offered conceptual analogies to 2D circle packings, influencing later geometric thought on dense arrangements. By the early 17th century, Johannes Kepler's conjecture (1611) on the optimal packing of spheres in three dimensions explicitly drew on hexagonal symmetry observed in nature, such as snowflakes, and spurred analogous inquiries into two-dimensional circle configurations.^[7] In the 19th century, mathematical rigor advanced the field significantly. Joseph Louis Lagrange demonstrated in 1773 that, among lattice packings, the hexagonal arrangement achieves the maximum density of \pi / \sqrt{12} \approx 0.9069. Carl Friedrich Gauss formalized this in 1831 by proving the hexagonal lattice to be the densest possible lattice packing of equal circles in the plane. Axel Thue extended these results beyond lattices, claiming in 1890 that the hexagonal packing is optimal overall using arguments based on circle coverings; however, gaps in this proof were addressed in his 1910 revision, establishing it as a foundational, albeit imperfect, milestone.^[6]^[8] The 20th century brought refinements and broader frameworks. László Fejes Tóth delivered the first fully rigorous proof in 1940, employing integral geometry to confirm the hexagonal lattice's optimality without lattice restrictions, surpassing Thue's approach in completeness. Fejes Tóth's seminal works, including his 1953 book Lagerungen in der Ebene, der Kugel und dem Raum, popularized systematic studies of packings, with the English term "circle packing" gaining prominence in the 1960s through translations and extensions of his research. These contributions solidified the infinite plane case while opening avenues for finite and curved variants.^[8] Post-2000 developments shifted toward computational exploration, particularly for finite packings. Projects like Packomania, maintained by Eckard Specht since the 1990s, have cataloged record-breaking configurations for packing equal circles in circles or squares, with notable improvements in the 2010s for n=10 to $100circles achieved through [global optimization](/page/Global_optimization) techniques by researchers including Marco Locatelli and Frédéric Schoen. In the 2020s, AI-driven methods, such as [reinforcement learning](/page/Reinforcement_learning) and neural network-guided placements, have accelerated optimizations for unequal circle packings, yielding denser arrangements in complex containers; for example, in July 2025, an AI-assisted approach surpassed Google's AlphaEvolve algorithm to set [a new world record](/page/A_New_World_Record) in the classic circle packing problem. Despite these advances, key challenges persist: the exact densest finite packings forn > 7$ remain unproven for many values as of 2025, with computational results serving as strong but inconclusive evidence.

Infinite Packings in the Plane

Densest Packings

The densest infinite packing of equal circles in the Euclidean plane is the hexagonal lattice packing, in which the centers of the circles form a triangular lattice. In this configuration, each circle is tangent to six neighboring circles arranged symmetrically around it, creating a honeycomb-like structure that maximizes coverage without overlaps. This arrangement is unique up to isometry among lattice packings and achieves the highest possible density for any circle packing in the plane.^[9] For circles of radius r = 1, the centers are positioned at lattice points generated by the basis vectors \mathbf{v_1} = (2, 0) and \mathbf{v_2} = (1, \sqrt{3}), yielding coordinates (2m + n, n\sqrt{3}) for integers m, n. The minimal distance between centers is 2, ensuring tangency. The unit cell of this lattice is a parallelogram spanned by \mathbf{v_1} and \mathbf{v_2}, with area given by the absolute value of the determinant:

|\det(\mathbf{v_1}, \mathbf{v_2})| = |2 \cdot \sqrt{3} - 0 \cdot 1| = 2\sqrt{3}.

This area corresponds to one circle per unit cell, so the area per circle is $2\sqrt{3}. The packing density \rho is then the ratio of the circle's area to this value:

\rho = \frac{\pi r^2}{2\sqrt{3}} = \frac{\pi}{2\sqrt{3}} = \frac{\pi}{\sqrt{12}} \approx 0.9069.

This density represents the proportion of the plane covered by the circles.^[8]^[6] The optimality of the hexagonal lattice was established by Thue's theorem, with the first rigorous proof provided by László Fejes Tóth in 1940. The proof demonstrates that no circle packing can exceed this density by showing that in any packing of unit circles, the average area of the Voronoi cells (regions closer to each center than to others) is at least $2\sqrt{3}, implying \rho \leq \pi / 2\sqrt{3}. Equality holds only for the hexagonal lattice, where each Voronoi cell is a regular hexagon of area exactly $2\sqrt{3}. Alternative approaches, such as those using Delaunay triangulation (the dual to the Voronoi diagram), bound the density by analyzing triangle areas and angles (constrained between \pi/3 and $2\pi/3), confirming the same upper limit. These methods rely on integral geometry and properties of convex sets to ensure no denser configuration exists.^[9]^[10]^[6]

Other Infinite Packings

The square lattice packing arranges equal circles such that their centers form a square grid, for example at coordinates (2m, 2n) for integers m, n and radius r = 1, where the distance between nearest neighbors is 2, ensuring tangency between horizontally and vertically adjacent circles. Diagonally adjacent circles do not touch, as their centers are separated by $2\sqrt{2} > 2. The packing density is given by \rho = \frac{\pi r^2}{(2r)^2} = \frac{\pi}{4} \approx 0.7854, representing the proportion of the plane covered by the circles.^[9] This density is achieved through a simple, periodic structure but is approximately 13% less efficient than the hexagonal packing's density of \pi / (2 \sqrt{3}) \approx 0.9069.^[9] Rectangular lattice packings generalize the square arrangement by using basis vectors of lengths $2a and $2b (with a \geq 1, b \geq 1) for unit circles, forming periodic structures with staggered or aligned rows. Among lattice packings, the hexagonal achieves the maximum density, while rectangular lattices provide a family of suboptimal periodic arrangements with densities \rho = \pi / (4ab) varying continuously from below \pi/4 (for highly elongated rectangles where \max(a,b) \gg 1) up to but not reaching the hexagonal density. The square lattice corresponds to the case a = b = 1, achieving \rho \approx 0.7854.^[9] Apollonian circle packings construct infinite arrangements in the plane by starting with three mutually tangent circles forming a curvilinear triangle and iteratively inscribing tangent circles within each interstice, following Descartes' Circle Theorem, which relates the curvatures (reciprocals of radii) of four mutually tangent circles. This recursive process generates a fractal-like structure unbounded across the plane in certain primitive configurations, filling curvilinear regions with circles of decreasing sizes. The packing is non-periodic and features infinitely many circles, with the total area covered approaching full density (residual unpacked set has Lebesgue measure zero), though the Hausdorff dimension of the residual set is approximately 1.30568.^[11] Random packings of equal circles in the plane are generated through stochastic processes modeled in statistical mechanics, such as analogs to Bernoulli site percolation on lattices or sequential addition algorithms that deposit circles without overlap until jamming occurs. These non-periodic configurations achieve an average packing density of approximately 0.82 through simulations of jammed states, higher than square lattice but below hexagonal due to inherent disorder and lack of long-range order.^[12]

Packings on Curved Surfaces

Packings on the Sphere

Circle packing on the sphere refers to the arrangement of non-overlapping spherical caps on the surface of the unit sphere S^2, where each cap corresponds to the central projection of a circle and the goal is to maximize the equal angular radius \theta for a fixed number n of caps or to fit the maximum number for a given total area.^[13] These caps must not overlap, meaning the geodesic distance between their centers exceeds $2\theta, and the problem arises in contexts like distributing points to maximize minimum separation.^[14] The Tammes problem, formulated in the 1930s by botanist P. M. L. Tammes while studying pollen grain pore distributions, specifically seeks the configuration of n equal non-overlapping circles on the unit sphere that maximizes their angular diameter.^[15] Proven optimal solutions exist for small n, such as n=3 with vertices of an equilateral triangle inscribed in a great circle, n=4 at the tetrahedral vertices, n=6 at the octahedral vertices, and n=12 at the icosahedral vertices, the latter achieving the kissing number of 12 on the sphere as proven by Schütte and van der Waerden. For n=24, an optimal arrangement corresponds to the snub cube vertices.^[16] The density \rho of such a packing is defined as the fraction of the sphere's surface covered by the caps, given by \rho = n \cdot \frac{2\pi (1 - \cos \theta)}{4\pi}, where \theta is the angular radius determined by the minimum center-to-center distance.^[13] For the icosahedral packing at n=12, \theta \approx 31.717^\circ, yielding \rho \approx 0.557. For larger n, optimal configurations are computationally determined, with records up to n=1000 showing arrangements that distort the icosahedral symmetry to accommodate more caps while approaching the spherical density limit. A 2022 iterated dynamic neighborhood search algorithm established new best-known results for 42 instances up to n=1080, including for moderate n, confirming near-icosahedral structures prevail for moderate n. Recent work as of 2024 has also explored packings on spherical caps, and a 2025 study provided a refined configuration for n=60, improving the minimum edge length slightly.^[16]^[13]^[17] Maintaining high symmetry where possible remains a focus in these refinements. The Tammes problem is analogous to the Thomson problem of minimizing Coulomb repulsion energy among n points on the sphere, first posed by J. J. Thomson in 1904; in the limit of infinite repulsion strength, the two coincide, as both favor maximal minimum distances.^[18]

Packings on Other Surfaces

Circle packings on non-spherical surfaces, such as the hyperbolic plane, cylinders, and tori, are influenced by the surface's curvature and topology, leading to configurations that differ significantly from those in Euclidean or spherical geometry. Negative curvature in hyperbolic surfaces enables packings with potentially higher densities than in the plane, while flat but periodic surfaces like cylinders and tori adapt lattice arrangements with densities depending on geometric parameters. In the hyperbolic plane, the negative curvature allows for circle packings that achieve densities exceeding the Euclidean optimum for congruent circles. Horocyclic packings, which use horocycles (circles of infinite radius centered at the boundary at infinity), can be used to construct triangulating packings on hyperbolic surfaces. For congruent circles on a hyperbolic surface of genus g ≥ 2, the density ρ is given by ρ = K · 2( cosh r - 1 ) / (g - 1 ), where K is the number of circles and r is the hyperbolic radius; as g → ∞, this approaches a maximum of 3π for certain configurations. On cusped hyperbolic surfaces, horocycle packings achieve maximal density 3π if and only if the surface is H^2 / Γ for a subgroup Γ of PSL_2(ℤ). With varying radii, packings can approach arbitrarily high local densities due to the exponential growth of area, as smaller circles can fill regions more efficiently in negatively curved space. In the Poincaré disk model of the hyperbolic plane, the Euclidean radius s of a hyperbolic circle of fixed hyperbolic radius R centered at hyperbolic distance d from the origin scales with the conformal factor, approximately s ≈ (1 - e^{-2(d + R)}) for large d, allowing local hyperbolic densities to increase as circles shrink in the model near the boundary while maintaining constant hyperbolic size.^[19] Cylindrical packings can be analyzed by unrolling the surface into an infinite strip of width equal to the cylinder's circumference C, with periodic boundary conditions in the circumferential direction. The density varies with the ratio C / (2r), where r is the circle radius; for C = 2r, only a single row is possible with density 1/2, while for larger C / (2r) ≈ √12, hexagonal-like arrangements approach the Euclidean maximum π / √12. Helical arrangements, where circles are staggered in rows winding around the cylinder, optimize density for intermediate ratios by reducing gaps, with numerical studies showing improved densities approaching the Euclidean hexagonal limit.^[20] On the torus, packings respect periodic boundary conditions, adapting planar lattices to the compact flat surface. For a square torus, the square lattice packing places circles at lattice points with centers separated by 2r, yielding density π / 4 ≈ 0.785, as each circle of area π r^2 occupies a unit cell of area 4 r^2. On the square torus, more complex periodic configurations with 6 or 7 circles per unit cell achieve densities of approximately 0.75 and 0.75, respectively, lower than the square lattice baseline of π/4 ≈ 0.785 for a single circle, though they provide baselines for finite approximations to infinite periodic extensions.^[21] For general surfaces, the Koebe–Andreev–Thurston theorem extends to hyperbolic and other Riemann surfaces, guaranteeing a circle packing whose tangency graph represents the surface's triangulation, with the packing determining a conformal structure. These packings produce rigid circle patterns that model the surface's geometry, useful for visualizing complex topologies. On hyperbolic surfaces, such packings are unique up to Möbius transformations and can incorporate horocycles on the boundary for cusped structures.^[22]

Finite Packings in Bounded Regions

Packings in General Bounded Areas

In finite packing problems, the objective is to arrange the maximum number of non-overlapping equal circles or to maximize the total packed area within a bounded domain, such as a rectangle or arbitrary polygon, where boundary constraints inevitably reduce the achievable density compared to infinite arrangements.^[23] Unlike infinite plane packings, finite domains introduce wasted space near the boundaries, leading to suboptimal configurations that prioritize fitting circles without overlap while respecting the enclosure's shape.^[24] Solving these problems is computationally challenging, as determining whether a given set of circles can be packed into a bounded region is NP-hard, a result established through reductions from known hard problems like 3-partition.^[25] Common algorithms include greedy placement methods, which iteratively position circles in the largest available void to build an initial configuration quickly, and more sophisticated optimization techniques such as simulated annealing, which explores local perturbations to escape suboptimal local minima by probabilistically accepting worse solutions at higher temperatures.^[26] Gradient ascent variants, often applied in continuous optimization frameworks, adjust circle positions via gradient-based updates to minimize energy functions representing overlaps and distances to boundaries, though they require differentiable formulations of the domain.^[27] The packing density in bounded regions asymptotically approaches the optimal infinite-plane density of \pi / \sqrt{12} \approx 0.9069 as the domain size grows large relative to the circle radius, but boundary effects cause a relative loss proportional to O(1/\sqrt{n}) for n circles, due to the perimeter's linear scaling with \sqrt{n} compared to the total area.^[28] For equal circles in a square, the achievable density typically decreases for small n before gradually increasing toward the infinite limit, with current record configurations tracked in databases like Packomania, which compile heuristically optimized packings up to n = 10,000 as of 2022.^[28] For unequal circles, the problem shifts toward maximizing the weighted total area packed, treating radii as variables in the optimization, though detailed methods for varying sizes are addressed separately.^[29]

Packings in Specific Containers

Circle packings in specific containers focus on arranging equal circles of unit radius within canonical bounded shapes to minimize the container size while avoiding overlaps. For the square container, optimal configurations are known and proven for small numbers of circles. For n=1, a single circle fits trivially with side length 2. For n=2, the circles are placed along the diagonal, achieving a minimal side length of $2 + \sqrt{2} \approx 3.414. For n=4, a 2×2 square grid arrangement is optimal, with side length 4. Configurations become more complex for n=5, involving a rotated central circle surrounded by four others in a cross-like pattern, proven optimal with side length approximately 4.828. Proven optima are known for n=1, 4, and 9 (3×3 grid, side length 6), while best-known arrangements for n=6, 7, 8 (compact layout, side ≈5.864), and 10 involve irregular or hexagonal-inspired layouts, with ongoing efforts to confirm optimality up to n=10.^[28] In a circular container, optimal packings for small n follow symmetric patterns, often with proven minimal enclosing radii. For n=1 to 6, configurations achieve hexagonal or regular polygonal symmetries, such as n=7 forming a central circle surrounded by six others in a hexagonal ring, with minimal radius R(7) = 3. For n=8 to 10, arrangements include a loose central circle with surrounding rings, yielding R(8) \approx 3.304, R(9) \approx 3.613, and R(10) \approx 3.813. Unlike higher-dimensional analogs where linear "sausage" arrangements compete with clustered forms, in two dimensions the lattice-based (hexagonal) packing prevails for all finite n in a circle, with no resolved debate favoring sausages; densities increase toward the infinite-plane hexagonal limit. For large n, best-known packings up to n=2600 approximate hexagonal lattices, achieving densities around 0.81 for n=100 and approaching 0.9069 asymptotically.^[30]^[3] Packings in an equilateral triangle emphasize layered triangular arrangements for small n, maximizing density within the minimal side length. For n=1, a single circle centers trivially; for n=3, one circle per corner yields side length $2 + 2/\sqrt{3} \approx 3.155; and for triangular numbers like n=10 (4 layers), a stacked hexagonal pattern is optimal. Densities for these are below 0.8, with upper bounds derived from geometric constraints, such as \delta \leq \frac{n \pi}{\sqrt{3} [ \sqrt{3} - \frac{3}{2} + \sqrt{\frac{1}{4} + 2n}]^2} exact for such n. Configurations for n=16 to 18 involve simulated annealing-optimized irregular layers, improving prior bounds.^[31]^[32] Variants in rectangles resemble square packings but allow elongated optima, while recent global optimization techniques in the 2020s have yielded best-known results for n up to 100 in squares, circles, and triangles, often via heuristic searches like iterated dynamic thresholding. An empirical approximation for the minimal enclosing radius R(n) in a circle is R(n) \approx \sqrt{\frac{n}{\pi \rho}}, where \rho \approx 0.9 reflects near-hexagonal densities for large n, providing scale for container sizing beyond exact solutions.^[33]^[34]

Packings of Unequal Circles

Methods for Different Radii

Circle packing with unequal radii addresses the arrangement of non-overlapping circles of varying sizes within a bounded region, encompassing several problem variants. Binary packings involve circles of only two distinct radii, often studied to explore density improvements over equal-radius cases by adjusting the ratio of sizes. Polydisperse packings feature a continuous or broad distribution of radii, mimicking real-world granular materials, while packings with prescribed radii fix specific sizes for each circle. The objectives typically include maximizing the total covered area via the sum of individual circle areas or achieving high density ρ = \sum_k \pi r_k^2 / A, where A is the container area, or minimizing the container size for a fixed set of circles.^[35]^[36]^[37] A foundational method for generating dense unequal packings is the Apollonian construction, which starts with three mutually tangent circles and iteratively inscribes new circles tangent to three existing ones in the resulting curvilinear triangular gaps, based on Apollonius' theorem that guarantees exactly two solutions for the new circle's radius and position. This iterative tangent-filling process produces fractal-like packings with infinitely many circles of decreasing sizes, achieving high local densities but not necessarily global optimality in finite settings.^[38] Greedy algorithms provide practical approaches for finite packings, sequentially inserting the largest feasible circle into the current configuration without overlap, often prioritizing placements that minimize wasted space near boundaries or existing circles. These methods, such as deterministic selection based on circle size and potential position, can be enhanced with local adjustments like rotation or shifting to escape poor local optima, yielding near-optimal results for rectangular or circular containers.^[39]^[40] Theoretical aspects include bounds on configuration stability and geometric constraints. Unlike equal-radius packings, unequal ones allow three mutually tangent circles to leave fillable curvilinear interstices rather than empty space, enabling denser arrangements but complicating rigidity. Bezdek established stability properties for dense circle packings, showing that small perturbations in positions lead to bounded displacements, with uniform stability ensuring the entire structure remains intact under limited forces.^[41]^[42] The non-overlap condition requires the distance d_{ij} between centers of circles i and j to satisfy d_{ij} \geq r_i + r_j, where equality denotes tangency.^[41]^[42] Optimization formulations treat unequal circle packing as a nonlinear program, minimizing a slack variable ε subject to d_{ij} \geq r_i + r_j + ε for all pairs i < j, with ε \geq 0 ensuring feasibility; this allows scaling circles uniformly if maximizing size under fixed container bounds. Solution techniques include global optimizers like monotonic basin hopping, which combines local searches with perturbations to navigate the non-convex search space. Computational tools such as MATLAB's fmincon solver or custom implementations of mixed-integer nonlinear programming handle these, often discretizing positions via binary variables for ring-like or grid-based placements. Density maximization in unequal cases lacks tight universal bounds like the equal-radius π / \sqrt{12}, as size variability permits higher local densities but introduces optimization challenges.^[43]^[44]

Notable Configurations and Results

One prominent example of an unequal circle packing is the Apollonian circle packing, a fractal configuration constructed iteratively from an initial set of three mutually tangent circles by filling each curvilinear triangular interstice with a circle tangent to the three bounding circles. This process relies on Descartes' circle theorem, which determines the curvature k_4 (the reciprocal of the radius) of the new circle as k_4 = k_1 + k_2 + k_3 \pm 2\sqrt{k_1 k_2 + k_1 k_3 + k_2 k_3}, where k_1, k_2, k_3 are the curvatures of the initial three circles.^[38] The resulting infinite packing features increasingly smaller nested circles that fill the plane densely, leaving a residual set—the limit set of unfilled points—with Lebesgue measure zero.^[45] The boundary of this residual set exhibits fractal properties, with a Hausdorff dimension of approximately 1.30568.^[45] The symmetries of the packing are captured by the Apollonian group, generated by inversions in the initial circles, which acts as a Kleinian group on the Riemann sphere.^[38] Another notable configuration is the set of Ford circles, introduced as a visualization of rational numbers. Each circle corresponds to a reduced fraction p/q and has radius $1/q^2, centered at (p/q, 1/q) above the x-axis, making it tangent to the x-axis and to neighboring circles if the fractions are adjacent in a Farey sequence of order q. This packing achieves tangency precisely between circles representing Farey neighbors, illustrating the density of rationals along the real line while maintaining non-overlap; the circles grow denser near the x-axis as q increases, reflecting the distribution in Farey sequences. An analog to the three-dimensional cannonball problem for unequal circles arises in pyramidal arrangements, where circles of decreasing radii are stacked in layers mimicking square pyramidal stacking of spheres projected onto a plane. Such configurations explore finite packings with hierarchical size distribution, often achieving structured densities through geometric progression of radii, though exact optima depend on specific radius sets.^[46] In recent computational efforts, evolutionary algorithms have produced near-optimal packings for small numbers of unequal circles in bounded regions like squares. For instance, configurations of 10 unequal circles (with radii often chosen as a decreasing sequence) have attained packing densities exceeding 0.8, surpassing the densities achieved with equal circles in the same finite container by exploiting size variation for better space utilization.^[47]

Applications

Mathematical and Theoretical Applications

The circle packing theorem, also known as the Koebe–Andreev–Thurston theorem, states that every finite simple planar graph is the contact graph of a circle packing in the plane, where circles are tangent if and only if the corresponding vertices are adjacent, and this representation is unique up to Möbius transformations.^[48] This result was first established by Paul Koebe in 1936 as a consequence of his generalization of the Riemann mapping theorem to multiply connected domains.^[49] Independently, E. M. Andreev proved a version for triangulated graphs in 1970, while William Thurston provided an elementary proof in 1985 using hyperbolic geometry, extending the theorem to include the bijectivity with conformal mappings.^[50] In graph theory, circle packings serve as representations of planar graphs as coin graphs or contact graphs, where vertices correspond to non-overlapping circles and edges to tangencies, enabling the study of structural properties like planarity and embedding. These representations exhibit rigidity: for maximal planar graphs, the packing is locally unique up to conformal equivalence, meaning small perturbations preserve the tangency structure only through rigid motions or scalings, which has implications for graph rigidity theory and the characterization of intersection graphs. Such rigidity arises from the geometric constraints of tangencies, analogous to bar-joint frameworks in discrete rigidity, and has been used to prove uniqueness in certain embeddings.^[51] Circle packings connect deeply to complex analysis by modeling discrete conformal maps, where sequences of packings converge to Riemann mappings from the disk to simply connected domains, as conjectured by Thurston and proved by Rodin and Sullivan in 1987.^[52] In hyperbolic geometry, Thurston's framework uses circle packings on the sphere or plane to represent ideal triangulations of surfaces, providing discrete analogs of uniformization theorems and enabling approximations of hyperbolic metrics via tangent circle configurations.^[50] In discrete geometry, circle packings relate to Delaunay triangulations and Voronoi diagrams through their centers and radical axes: the tangency graph of a packing forms the weighted Delaunay triangulation of the circle centers, with weights equal to the squared radii, while the Voronoi cells correspond to regions equidistant in the power diagram sense, facilitating the analysis of tessellations and proximity structures in packings.^[53] This duality aids in constructing optimal triangulations from packings and studying medial axes in geometric configurations.^[54] Despite advances, several problems remain unsolved, including the exact densest packings of equal circles in a square for n=10 and 11, where current configurations achieve densities of approximately 0.69 and 0.70 but lack rigorous proofs of optimality.^[28] For unequal circle packings, the asymptotic growth rate of achievable densities—particularly the precise constant in bounds approaching 1 as radius distributions vary—remains open, though partial progress has been made using AI-driven evolutionary algorithms in 2025.

Practical and Engineering Applications

In materials science, circle packing models are employed to simulate the arrangement of particles in granular materials and colloidal suspensions, providing insights into void formation and mechanical properties of composites. For instance, dense circle packings in arbitrary domains approximate the configurations of monodisperse spheres in 2D slices of granular systems, enabling predictions of packing fractions that influence porosity and stress distribution in engineering materials like soils or powders.^[55] These models draw from experimental observations of random packings in colloids, where packing densities around 0.64 for disordered states mirror those in granular matter, aiding the design of composite materials with optimized void fractions for enhanced strength.^[56] In colloidal self-assembly, packing arguments rationalize crystal structures, with hexagonal close packings achieving densities up to 0.907, informing the fabrication of materials with controlled defects for applications in filtration and catalysis.^[57] Circle packing algorithms find application in computer graphics for texture atlas generation and parameterization of surfaces, where they minimize distortion in mapping 2D textures onto 3D models by representing meshes as tangent circle configurations. This approach, based on least squares conformal mappings, ensures seamless texture application across irregular geometries, reducing seams and improving rendering efficiency in visualization software.^[58] In neuroscience, circle packings enable conformal mapping of cortical surfaces, producing flat representations of the brain's folded structure to analyze connectivity, functional regions, and morphological features while preserving angular relationships.^[59] In VLSI design, analogous disk packing techniques optimize the placement of circular components such as vias or sensors on chips, maximizing density while avoiding overlaps to enhance signal integrity and reduce manufacturing defects, though rectangular approximations are more common for standard cells. Computational algorithms from bounded area packings are occasionally adapted for these layouts to achieve near-optimal utilization of silicon area.^[60] In wireless networks, circle packing models the coverage areas of base stations as non-overlapping disks to maximize signal reach while minimizing interference, particularly in deployments using unmanned aerial vehicles (UAVs) as aerial base stations. By applying circle packing theory, optimal 3D positions for UAVs can increase total coverage by up to 20% in indoor environments compared to uniform grids, ensuring efficient spectrum use in dense urban settings.^[61] This method extends to ground-based networks, where hexagonal circle packings approximate the ideal arrangement for cellular base stations, achieving coverage densities that support high-throughput 5G deployments with reduced overlap. Nanotechnology leverages circle packing for designing ordered arrays of nanoparticles, simulating self-assembly processes to create photonic crystals with tailored optical properties. Close-packed nanoparticle arrays, mimicking 2D projections of face-centered cubic lattices, form "nanofluidic crystals" that control fluid flow at the nanoscale, with packing densities dictating bandgap formation for applications in sensors and filters.^[62] For unequal radii, as in heterogeneous nanoparticle systems, packing configurations inform the assembly of plasmonic photonic crystals, where densities above 0.8 enable enhanced light-matter interactions for optoelectronic devices.^[63] Recent advances in the 2020s integrate AI-driven circle packing optimizations for battery cell arrangements and 3D printing supports, enhancing energy density and structural integrity. In electric vehicle batteries, hexagonal circle packings of cylindrical cells, such as Tesla's 4680 format, achieve packing efficiencies up to 0.907, reducing dead space and improving thermal management in modules that support approximately 170–180 Wh/kg at the pack level (as of 2025).^[64] For 3D printing, packing algorithms optimize infill patterns with circular supports, minimizing material use while maximizing print speed, as seen in conformal battery designs that integrate seamlessly into compact devices.^[65]

References

[1]
[PDF] Circle Packing: A Mathematical Tale - UTK Math
These packings are configurations of circles satisfying preassigned patterns of tangency, and we will be concerned here with their creation, manip- ulation, and ...Missing: scholarly | Show results with:scholarly
[2]
Introduction to circle packing: The theory of discrete analytic ...
Feb 19, 2009 · Two important stories in the recent history of mathematics are those of the ge- ometrization of topology and the discretization of geometry.Missing: scholarly | Show results with:scholarly
[3]
[PDF] Dense packings of congruent circles in a circle - UCSD Math
Two packing algorithms are discussed, and the best packings found of up to 65 circles are presented. 1. Introduction. Problems of packing congruent circles in ...Missing: scholarly | Show results with:scholarly
[4]
Circle Packing: Experiments in Discrete Analytic Function Theory
A circle packing is a con guration of circles hav- ing a prescribed pattern of tangencies. Our in- terest lies in maps from one circle packing to an- other ...
[5]
Kissing Numbers, Sphere Packings, and Some Unexpected Proofs
It is a simple exercise (recommended) to prove, for dimension two, that the “obvious” hexagonal packing of equal-sized disks (two-dimensional balls) in the ...
[6]
[PDF] A Simple Proof of Thue's Theorem on Circle Packing - arXiv
Sep 22, 2010 · Since the density of a circle configuration C is always less than or equal to the density of any satura- tion of C. Hence, we only need to ...
[7]
(PDF) A Short History of Packing Problems - ResearchGate
Aug 3, 2025 · In particular the problem of the densest close packing of spheres has become celebrated as the Kepler Problem. The history of the subject is ...
[8]
[PDF] revisiting the hexagonal lattice: on optimal lattice circle packing
Thus Theorem 1.1 implies right away that only a WR lattice can maximize lattice packing density. Our proof of Theorem 1.1 emphasizes the importance of WR ...
[9]
Global optimization method for finding dense packings of equal ...
This paper considers the problem of finding the densest packing of N (N = 1, 2, ...) equal circles in a circle.
[10]
The chore of packing just got faster and easier | MIT News
Jul 6, 2023 · An MIT-led team introduces a new computational method that facilitates the dense placement of objects inside a rigid container.
[11]
Circle Packing -- from Wolfram MathWorld
Gauss proved that the hexagonal lattice is the densest plane lattice packing, and in 1940, L. Fejes Tóth proved that the hexagonal lattice is indeed the densest ...Missing: date | Show results with:date
[12]
[PDF] Minimal Area of a Voronoi Cell in a Packing of Unit Circles - arXiv
Nov 7, 2022 · We present a new self-contained proof of the well-known fact that the minimal area of a Voronoi cell in a unit circle packing is equal to 2√3, ...
[13]
Apollonian circle packings: number theory - ScienceDirect.com
The exponent e of any bounded Apollonian circle packing is equal to the Hausdorff dimension α of the residual set of any Apollonian circle packing. The ...
[14]
A geometric probabilistic approach to random packing of hard disks ...
May 16, 2023 · In this paper the random packing fraction of hard disks in a plane is analyzed, following a geometric probabilistic approach.
[15]
[2406.02851] Circle packing on spherical caps - arXiv
Jun 5, 2024 · This problem has been considered before only in the limit cases of circle packing inside a circle and on a sphere (Tammes problem), whereas all ...
[16]
Improved packing of equal circles on a sphere and rigidity of its graph
Oct 24, 2008 · How must n equal non-overlapping circles be packed on a sphere so that the angular diameter of the circles will be as great as possible?Missing: original | Show results with:original
[17]
Packing of twinned circles on a sphere - Journals
Jul 11, 2006 · This is the Tammes (1930) problem. Proven solutions are available for n=1–12 and 24 (Fejes Tóth 1964), and conjectural solutions for other ...
[18]
Iterated dynamic neighborhood search for packing equal circles on ...
In this work, we investigate the equal circle packing problem on a sphere (ECPOS), which consists in packing N equal non-overlapping circles on a unit ...
[19]
[PDF] On the Tammes Problem for 60 Points
Jan 4, 2025 · Abstract. In an attempt to solve the Tammes problem for 60 points, we analyzed the positioning obtained by Laszlo Hars [1].Missing: records | Show results with:records
[20]
[math/0410324] The kissing problem in three dimensions - arXiv
The first proof that k(3)=12 was given by Schütte and van der Waerden only in 1953. In this paper we present a new solution of the Newton-Gregory problem ...
[21]
[PDF] arXiv:2010.12028v3 [math.GT] 18 Feb 2022
Feb 18, 2022 · We discuss several ways of packing a hyperbolic surface with circles (of either varying radii or all being congruent) or horocycles, and note ...
[22]
Theory of cylindrical dense packings of disks - ResearchGate
Aug 6, 2025 · We have previously explored cylindrical packings of disks and their relation to sphere packings. Here we extend the analytical treatment of ...
[23]
[PDF] Optimal packings of congruent circles on a square flat torus - arXiv
Dec 6, 2012 · Abstract. We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, ...Missing: boundary | Show results with:boundary
[24]
[PDF] The Approximation of Conformal Structures via Circle Packing
The same result holds in hyperbolic geometry, where g is also allowed to assume the value +1. In other words, there exists an essentially unique circle packing.
[25]
Adaptive simulated annealing with greedy search for the circle bin ...
We introduce a new bin packing problem, termed the circle bin packing problem with circular items (CBPP-CI). The problem involves packing all the circular ...
[26]
[PDF] Efficient algorithms for the dense packing of congruent circles inside ...
Jan 31, 2021 · We study dense packings of a large number of congruent non-overlapping circles inside a square by looking for configurations which maximize the.
[27]
[1008.1224] Circle Packing for Origami Design Is Hard - arXiv
Aug 6, 2010 · We show that deciding whether a given set of circles can be packed into a rectangle, an equilateral triangle, or a unit square are NP-hard ...
[28]
An efficient quasi-physical quasi-human algorithm for packing equal ...
CPP has been proven to be NP-hard (Demaine et al., 2010); as such, it is difficult to find an exact solution in polynomial time, even for some specific ...
[29]
Adaptive Simulated Annealing with Greedy Search for the Circle Bin ...
Aug 6, 2021 · We introduce a new bin packing problem, termed the circle bin packing problem with circular items (CBPP-CI). The problem involves packing all the circular ...
[30]
The best known packings of equal circles in a square
Aug 22, 2022 · This document lists best known packings of equal circles in a square, up to N=10000. Packing is equivalent to distributing points in a square.
[31]
An action-space-based global optimization algorithm for packing ...
This paper proposes an action-space-based global optimization (ASGO) approach for the problem of packing unequal circles into a square container
[32]
The best known packings of equal circles in a circle
The best known packings of equal circles in a circle (complete up to N = 2600) Last update: 25-Dec-2024Missing: Gravel finite
[33]
[PDF] Note Packing 16, 17 or 18 circles in an equilateral triangle
We present new, efficient packings for 16, 17 and 18 congruent circles in an equilateral triangle. The results have been found by the use of simulated annealing ...
[34]
[PDF] UPPER BOUND OF DENSITY FOR PACKING OF EQUAL CIRCLES ...
In the paper we will give heuristic upper bounds for the density of packings of non-overlapping equal circles in a square, an equilateral triangle, and a ...<|separator|>
[35]
Packomania
Packings of equal and unequal circles in fixed-sized containers with maximum packing density. The probably densest irregular packing ever found by computers ...Missing: finite 2010s
[36]
[PDF] Iterated dynamic thresholding search for packing equal circles ... - HAL
Jul 22, 2024 · The second experiment aims to assess the proposed IDTS algorithm on large instances with N ≥ 101 and up to N = 320 by making a comparison with ...
[37]
Density of binary disc packings: Playing with stoichiometry
A disc packing (or circle packing) is a set of interior-disjoint discs in the Euclidean plane. Its density δ is the proportion of the plane covered by the ...Missing: methods | Show results with:methods
[38]
Circle Packing Problem Using Nature-Inspired Optimization ...
Mar 16, 2024 · The circle packing problem involves fitting the largest circle into a space with other circles of different radii and centers. It is an NP-hard ...Missing: methods unequal<|control11|><|separator|>
[39]
[PDF] Computer generation of dense polydisperse sphere packings
Nov 8, 2002 · In this paper, we study the maximum packing fraction obtainable for three-dimensional amorphous binary packings using the L–S algorithm as a ...
[40]
[math/0009113] Apollonian Circle Packings: Number Theory - arXiv
Apollonian circle packings arise by repeatedly filling the interstices between mutually tangent circles with further tangent circles. It is possible for every ...Missing: method | Show results with:method
[41]
Greedy algorithms for packing unequal circles into a rectangular ...
Oct 13, 2004 · In this paper, we develop two greedy algorithms to pack unequal circles into a rectangular container. They are both deterministic and ...Missing: algorithm circle
[42]
[PDF] Greedy Algorithms for Packing Unequal Circles into a - MIS
We propose two greedy algorithms to pack unequal circles into a 2D rectangular con- tainer. The first algorithm, denoted by В1. 0, selects the next circle to ...
[43]
A stability property of the densest circle packing
A new stability property of the densest circle packing in the plane is proved. This property is related to a conjecture ofL. Fejes Tóth.
[44]
(PDF) Finite and Uniform Stability of Sphere Packings - ResearchGate
Aug 7, 2025 · The main purpose of this paper is to discuss how firm or steady certain known ball packing are, thinking of them as structures.
[45]
[PDF] Solving the problem of packing equal and unequal circles in a ...
In this paper we propose a Monotonic Basin Hopping approach and its population-based variant Population Basin Hopping to solve the problem of packing equal and ...Missing: 2020s | Show results with:2020s
[46]
[PDF] Exact Methods for Recursive Circle Packing - OPUS
Jan 2, 2019 · The key idea of the developed MINLP is to use binary variables in order to indicate whether a ring is packed inside another larger ring or ...
[47]
[PDF] Apollonian circle packings: number theory - UCSD Math
The exponent e of any bounded Apollonian circle packing is equal to the Hausdorff dimension a of the residual set of any Apollonian circle packing. The ...
[48]
NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY
Dec 3, 2003 · • Packing: A circle packing P for K is a configuration of ... • A Differential Inequality for the Isoperimetric Profile, Vincent Bayle.
[49]
The best known packings of unequal circles in a square
Oct 28, 2015 · The best known packings of unequal circles with integer radii in a square (complete up to N = 72) Last update: 28-Oct-2015Missing: packomania | Show results with:packomania
[50]
[PDF] Variational principles for circle patterns and Koebe's theorem - arXiv
A circle packing is a configuration of disjoint discs which may touch but not intersect. In 1936, Koebe published the following theorem about circle packings.
[51]
[PDF] THE CIRCLE PACKING THEOREM - AMS Tesi di Laurea
In this chapter we define circle packings, their graphs and we give different equivalent statements of the Koebe-Andeev-Thurston theorem. As mentioned in the ...
[52]
[PDF] William P. Thurston The Geometry and Topology of Three-Manifolds
... circle packing. The existence of other geometric patterns of circles in R2 may also be deduced from Andreev's theorem. For instance, it gives necessary and ...<|control11|><|separator|>
[53]
[PDF] Coin representation - D-MATH
We prove Koebe's important theorem on representing a planar graph by touching circles [5], and its extension to a Steinitz representation, the Cage Theorem.<|control11|><|separator|>
[54]
[PDF] a probabilistic proof of thurston's conjecture on circle packings
This is the principal theme of the paper: working in hyperbolic geometry, we carry out a thorough study of an individual circle packing P and the dynamics ...<|control11|><|separator|>
[55]
[PDF] Exploring Circle Packing Algorithms - Don Sheehy
The most natural approach is to draw circles and produce the weighted Delaunay triangulation of the circles. Input is given by clicking a center and dragging to ...<|separator|>
[56]
[PDF] The Voronoi Cell in a saturated Circle Packing - EPub Bayreuth
May 13, 2019 · This proof is assigned to Thue 1910 and was reworked several times [9]. Zong gave a book proof in [3] using the concept of Voronoi cells and ...
[57]
ShinkaEvolve: Evolving New Algorithms with LLMs ... - Sakana AI
Sep 25, 2025 · September 25, 2025. ShinkaEvolve produced algorithms that found a state-of-the-art Circle Packing solution. We introduce ShinkaEvolve, an ...
[58]
Circle packing in arbitrary domains | Physics of Fluids - AIP Publishing
Dec 13, 2023 · We describe an algorithm that allows one to find dense packing configurations of a number of congruent disks in arbitrary domains in two or ...
[59]
Random packing of colloids and granular matter - ResearchGate
This thesis deals with the random packing of colloids and granular matter. A random packing is a stable disordered collection of touching particles, ...
[60]
Relevance of packing to colloidal self-assembly - PMC - NIH
Since the 1920s, packing arguments have been used to rationalize crystal structures in systems ranging from atomic mixtures to colloidal crystals. Packing ...Missing: granular | Show results with:granular
[61]
[PDF] Least Squares Conformal Maps for Automatic Texture Atlas ...
propose a method based on circle packings, which are certain configurations of cir- cles with specified pattern of tangencies known to provide a way to ...
[62]
[PDF] VLSI cell placement techniques - Electrical and Computer Engineering
a VLSI chip. The objective of this paper is to present a comprehensive survey of the various cell placement techniques, with emphasis on standard ce11and macro.
[63]
[1705.09772] Maximizing Indoor Wireless Coverage Using UAVs ...
May 27, 2017 · In the first method, we utilize circle packing theory to determine the 3-D locations of the UAVs in a way that the total coverage area is ...
[64]
Nanofluidics in a Close-Packed Nanoparticle Array - PMC - NIH
Like the term “photonic crystal” in photonic applications, close-packed nanoparticle array is named as “nanofluidic crystal” in nanofluidics. Figure 1 ...
[65]
Plasmonic Nanocrystal Arrays on Photonic Crystals with Tailored ...
The PPMs consist of gold nanocrystal (AuNC) arrays (3rd-tier) anchored on a hexagonal nanopattern (2nd-tier) assembled from silica nanoparticles (SiO 2 NPs)
[66]
Analysis of System Packing Efficiency and Cell Types - MDPI
Dec 10, 2020 · This is very likely due to the fact that the round cells can inherently be packed less dense than prismatic or pouch cells due to their shape.
[67]
The Role of 3D Printing in Battery Manufacturing - AZoM
Nov 7, 2024 · The 3D printing technology used enables robust design configurations, allowing the batteries to withstand higher tensile stress. Researchers ...