An Algorithm for Packing Balls of Two Types in a Three-Dimensional Set with a Non-Euclidean Metric


  • A.L. Kazakov V.M. Matrosov Institute of System Dynamics and Control Theory SB RAS
  • A.A. Lempert Matrosov Institute of System Dynamics and Control Theory SB RAS
  • C.T. Ta Irkutsk National Research Technical University


optimal packing of balls of different radii, computational algorithm, billiard modeling, optical-geometric method, software package


The problem of packing balls of two types into a closed bounded set in three-dimensional space with the Euclidean metric and a special non-Euclidean metric. It is required to maximize the radius of the balls for a given number of balls of each type and a known ratio of radii. We propose a omputational algorithm based on a combination of the billiard modeling method and the optical-geometric approach employing the fundamental physical principles of Fermat and Huygens. The results of numerical experiments are discussed.


A.L. Kazakov

A.A. Lempert

C.T. Ta


  1. Castillo I., Kampas F.J., Pint´er J.D. Solving circle packing problems by global optimization: numerical results and industrial applications // European Journal of Operational Research. 2008. 191, N 3. 786–802.
  2. Harary F., Randolph W., Mezey P.G. A study of maximum unit-circle caterpillars — tools for the study of the shape of adsorption patterns // Discrete Applied Mathematics. 1996. 67, N 1–3. 127–135.
  3. Wang J. Packing of unequal spheres and automated radiosurgical treatment planning // Journal of Combinatorial Optimization. 1999. 3. 453–463.
  4. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem // Computational Geometry. 2010. 43, N 5. 535–553.
  5. Hales T. Cannonballs and honeycombs // Notices of the American Mathematical Society. 2000. 47, N 4. 440–449.
  6. Stoyan Y., Yaskov G. Packing identical spheres into a rectangular parallelepiped // Intelligent Decision Support. Wiesbaden: Betriebswirtschaftlicher Verlag Dr. Th. Gabler, 2008. 47–67.
  7. Stoyan Yu.G., Yaskov G. Packing identical spheres into a cylinder // International Transactions in Operational Research. 2009. 17, N 1. 51–70.
  8. Huang W., Yu L. Serial symmetrical relocation algorithm for the equal sphere packing problem. Ithaca: Cornell Univ. Library, 2012. Available at
  9. Mughal A., Chan H., Weaire D., Hutzler D. Dense packings of spheres in cylinders: simulations // Physical Review E. 2012. 85. doi 10.1103/PhysRevE.85.051305.
  10. Fu L., Steinhardt W., Zhaod H., Socolar J.E.S., Charbonneau P. Hard sphere packings within cylinders // Soft Matter. 2016. 12. 2505–2514.
  11. Scheithauer G., Stoyan Yu., Yaskov G. Packing non-equal spheres into containers of different shapes. 2013.
  12. Stoyan Yu.G., Scheithauer G., Yaskov G.N. Packing unequal spheres into various containers // Cybernetics and Systems Analysis. 2016. 52, N 3. 419–426.
  13. Khlud O.M., Yaskov G.N. Packing homothetic spheroids into a larger spheroid with the jump algorithm // Control, Navigation and Communication Systems. 2017. 6, N 46. 131–135.
  14. Kubach T., Bortfeldt A., Tilli T., Gehring H. Parallel greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid. 2009.
  15. Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid // Asia Pacific Journal of Operational Research. 2011. 28, N 6. 739–753.
  16. Huang W.Q., Li Y., Akeb H., Li C.M. Greedy algorithms for packing unequal circles into a rectangular container // Journal of the Operational Research Society. 2005. 56, N 5. 539–548.
  17. Hifi M., Yousef L. Width beam and hill-climbing strategies for the three-dimensional sphere packing problem // 2014 Federated Conference on Computer Science and Information Systems. New York: IEEE Press, 2014. 421–428.
  18. Yamada S., Kanno J., Miyauchi M. Multi-sized sphere packing in containers: optimization formula for obtaining the highest density with two different sized spheres // IPSJ Online Transactions. 2011. 4. 126–133.
  19. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. 50–57.
  20. Бухаров Д.С., Казаков А.Л. Программная система “ВИГОЛТ” для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование. 2012. 13 65–74.
  21. Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. 87–100.
  22. Kazakov A.L., Lempert A.A. On mathematical models for optimization problem of logistics infrastructure // International Journal of Artificial Intelligence. 2015. 13, N 1. 200–210.
  23. Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Вычислительные методы и программирование. 2015. 16. 307–317.
  24. Казаков А.Л., Лемперт A.A., Нгуен Г.Л. Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой // Вычислительные методы и программирование. 2016. 17. 177–188.
  25. Kazakov A.L., Lempert A.A., Ta T.T. The sphere packing problem into bounded containers in three-dimension non-Euclidean space // IFAC-PapersOnLine. 2018. 51, N 32. 782–787.
  26. Kazakov A.L., Lempert A.A., Ta T.T. On the algorithm for equal balls packing into a multi-connected set // VIth International Workshop on Critical Infrastructures: Contingency Management, Intelligent, Agent-Based, Cloud Computing and Cyber Security (IWCI 2019). Paris: Atlantis Press, 2019. 216–222.
  27. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989.
  28. Graham R.L., Lubachevsky B.D., Nurmela K.J., Ostergard P.R.J. Dense packings of congruent circles in a circle // Discrete Mathematics. 1998. 181, N 1–3. 139–154.



How to Cite

Kazakov A.L., Lempert A.A., Ta C.T. An Algorithm for Packing Balls of Two Types in a Three-Dimensional Set With a Non-Euclidean Metric // Numerical methods and programming. 2020. 21. 152-163



Section 1. Numerical methods and applications