An algorithm for packing balls of two types in a three-dimensional set with a non-euclidean metric

Authors

DOI:

https://doi.org/10.26089/NumMet.v21r213

Keywords:

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

Abstract

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.

Author Biographies

A.L. Kazakov

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS),
• Chief Researcher

A.A. Lempert

Matrosov Institute for System Dynamics and Control Theory of SB RAS (IDSTU SB RAS),
• Leading Researcher

C.T. Ta

Irkutsk National Research Technical University,
•  Graduate Student

References

  1. Castillo I., Kampas F.J., Pintér 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 https://arxiv.org/abs/1202.4149.
  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. http://www.math.tu-dresden.de/~scheith/ABSTRACTS/2013-spheres.html.
  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. https://www.fernuni-hagen.de/wirtschaftswissenschaft/download/beitraege/db440.pdf.
  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.
New computational technologies

Downloads

Published

2020-05-20

How to Cite

Казаков А.Л., Лемперт А.А., Та Ч.Т. 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. doi 10.26089/NumMet.v21r213

Issue

Vol. 21 (2020): Issue 2.

Section

Section 1. Numerical methods and applications