Skip to main content
Springer Nature Link
Log in

Efficient Algorithms for the Dense Packing of Congruent Circles Inside a Square

  • Published:
Save article
View saved research
Discrete & Computational Geometry Aims and scope Submit manuscript

Abstract

We study dense packings of a large number of congruent non-overlapping circles inside a square by looking for configurations which maximize the packing density, defined as the ratio between the area occupied by the disks and the area of the square container. The search for these configurations is carried out with the help of two algorithms that we have devised: a first algorithm is in charge of obtaining sufficiently dense configurations starting from a random guess, while a second algorithm improves the configurations obtained in the first stage. The algorithms can be used sequentially or independently. The performance of these algorithms is assessed by carrying out numerical tests for configurations with a large number of circles.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. The optimal solutions for \(N=31,32,33\) have been proved recently by Markót in [12].

  2. Notice for example that the density reported for \(N=2000\) is smaller than the density reported for \(N=500\).

  3. The ideas at the base of our algorithm, however, can be generalized to containers of different shape.

  4. Kepler’s conjecture, regarding sphere packing in three-dimensional Euclidean space, has been proved only in recent times by Thomas Hales [9], despite being put forward by Kepler in 1611. Needless to say, that the optimal configuration has been empirically known to generations of greengrocers without a formal training in mathematics!

  5. A similar problem was observed by one of us, while studying the Thomson’s problem in a disk [1]: in that case, it was found that the energies of the configurations have a strong dependence on the number of border points and that the search for a global minimum of the total energy requires to generate configurations with the appropriate number of border points.

  6. Of course, different choices for \(\alpha \) could be considered, keeping in mind that we want \(\mathcal {F}\) to provide sufficient border repulsion at the start of the process and \(\mathcal {F}\rightarrow 1\) at the end of the process.

  7. The only criterium that we have used to select a configuration has been to require a large number of circles and that it had been obtained before.

  8. The gaussian fit may be used to roughly estimate the number of trials needed to obtain a configuration with density above a certain value.

  9. It is easy to convince oneself that an appropriate rotation of 0, \(\pi /2\), \(\pi \), or \(3\pi /2\) radians, possibly followed by a reflection about the line \(y=x\), will always bring the center of mass of an arbitrary configuration to lie in this region.

  10. D.J. Wales, private communication, 2021.

  11. H. Szabolcs, LaTeX typesetting in Mathematica. http://szhorvat.net/pelican/latex-typesetting-in-mathematica.html

  12. Mathematica, v. 12.3.1. Wolfram Research, Inc.

References

  1. Amore, P.: Comment on “Thomson rings in a disk”. Phys. Rev. E 95(2), # 026601 (2017)

  2. Aste, T., Weaire, D.: The Pursuit of Perfect Packing. Taylor & Francis, New York (2008)

    MATH  Google Scholar 

  3. Baker, J., Kudrolli, A.: Maximum and minimum stable random packings of Platonic solids. Phys. Rev. E 82(6), # 061304 (2010)

  4. de Bono, J.P., McDowell, G.R.: On the packing and crushing of granular materials. Int. J. Solids Struct. 187, 133–140 (2020)

    Article  Google Scholar 

  5. Bowick, M., Cacciuto, A., Nelson, D.R., Travesset, A.: Crystalline order on a sphere and the generalized Thomson problem. Phys. Rev. Lett. 89(18), # 185502 (2002)

  6. Erber, T., Hockney, G.M.: Equilibrium configurations of \(N\) equal charges on a sphere. J. Phys. A: Math. Gen. 24(23), L1369–L1377 (1991)

    Article  Google Scholar 

  7. Fejes, L.: Über die dichteste Kugellagerung. Math. Z. 48, 676–684 (1943)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fua, P., Lis K.: Comparing Python, Go, and C++ on the \(N\)-queens problem (2020). arXiv:2001.02491

  9. Hales, T.C.: A proof of the Kepler conjecture. Ann. Math. 162(3), 1065–1185 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  10. Hifi, M., M’hallah, R.: A literature review on circle and sphere packing problems: models and methodologies. Adv. Oper. Res. 2009, # 150624 (2009)

  11. Lam, S.K., Pitrou, A., Seibert S.: Numba: a LLVM-based Python JIT compiler. In: 2nd Workshop on the LLVM Compiler Infrastructure in HPC (Austin 2015), # 6. ACM, New York (2015)

  12. Markót, M.Cs.: Improved interval methods for solving circle packing problems in the unit square. J. Glob. Optim. 81(3), 773–803 (2021)

  13. Nurmela, K.J., Östergård, P.R.J.: Packing up to \(50\) equal circles in a square. Discret. Comput. Geom. 18(1), 111–120 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  14. Peikert, R., Würtz, D., Monagan, M., de Groot, C.: Packing circles in a square: a review and new results. In: System Modelling and Optimization (Zürich 1991). Lecture Notes in Control and Information Sciences, vol. 180, pp. 45–54. Springer, Berlin (1992)

  15. Pérez-Garrido, A., Ortuño, M., Cuevas, E., Ruiz, J.: Many-particle jumps algorithm and Thomson’s problem. J. Phys. A: Math. Gen. 29(9), 1973–1978 (1996)

    Article  MATH  Google Scholar 

  16. Pouliquen, O., Nicolas, M., Weidman, P.D.: Crystallization of non-Brownian spheres under horizontal shaking. Phys. Rev. Lett. 79(19), 3640–3643 (1997)

    Article  Google Scholar 

  17. Salerno, K.M., Bolintineanu, D.S., Grest, G.S., Lechman, J.B., Plimpton, S.J., Srivastava, I., Silbert, L.E.: Effect of shape and friction on the packing and flow of granular materials. Phys. Rev. E 98(5), # 050901 (2018)

  18. Schaer, J.: The densest packing of \(9\) circles in a square. Can. Math. Bull. 8(3), 273–277 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  19. Schaer, J., Meir, A.: On a geometric extremum problem. Can. Math. Bull. 8(1), 21–27 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  20. Specht, E.: Packings of equal and unequal circles in fixed-sized containers with maximum packing density. In: Packomania (2020). http://hydra.nat.uni-magdeburg.de/packing/

  21. Stokely, K., Diacou, A., Franklin, S.V.: Two-dimensional packing in prolate granular materials. Phys. Rev. E 67(5), # 051302 (2003)

  22. Szabó, P.G., Markót, M.Cs., Csendes, T., Specht, E., Casado, L.G., García, I.: New Approaches to Circle Packing in a Square. Springer Optimization and Its Applications, vol. 6. Springer, New York (2007)

  23. Wales, D.J.: Chemistry, geometry, and defects in two dimensions. ACS Nano 8(2), 1081–1085 (2014)

    Article  Google Scholar 

  24. Wales, D.J., Ulker, S.: Structure and dynamics of spherical crystals characterized for the Thomson problem. Phys. Rev. B 74(21), # 212101 (2006)

Download references

Acknowledgements

The authors would like to thank Dr Roberto Sáenz, Dr Eckard Specht, and Dr David Wales, for reading the manuscript and for their valuable comments. The research of P.A. was supported by the Sistema Nacional de Investigadores (México). P.A. would like to thank the Universidad de Colima, and in particular M.C. Miguel Angel Rodríguez-Ortiz for the support in the creation of the Repository of Computational Physics and Applied Mathematics at the Universidad de Colima. The plots in this paper have been plotted using MaTeX and Mathematica

Author information

Authors and Affiliations

  1. Facultad de Ciencias, CUICBAS, Universidad de Colima, Bernal Díaz del Castillo 340, Colima, Colima, Mexico

    Paolo Amore

  2. Facultad de Ciencias, Universidad de Colima, Bernal Díaz del Castillo 340, Colima, Colima, Mexico

    Tenoch Morales

Authors
  1. Paolo Amore
    View author publications

    Search author on:PubMed Google Scholar

  2. Tenoch Morales
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Paolo Amore.

Ethics declarations

Conflicts of interest

The authors declare that they have no conflict of interest.

Additional information

Editor in Charge: Kenneth Clarkson

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Amore, P., Morales, T. Efficient Algorithms for the Dense Packing of Congruent Circles Inside a Square. Discrete Comput Geom 70, 249–267 (2023). https://doi.org/10.1007/s00454-022-00425-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Version of record:

  • Issue date:

  • DOI: https://doi.org/10.1007/s00454-022-00425-5

Keywords

Mathematics Subject Classification

Profiles

  1. Paolo Amore View author profile