An algorithm for packing balls of two types in a three-dimensional set with a non-euclidean metric
DOI:
https://doi.org/10.26089/NumMet.v21r213Keywords:
optimal packing of balls of different radii, computational algorithm, billiard modeling, optical-geometric method, software packageAbstract
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.
References
- 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.
- 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.
- Wang J. Packing of unequal spheres and automated radiosurgical treatment planning // Journal of Combinatorial Optimization. 1999. 3. 453–463.
- Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem // Computational Geometry. 2010. 43, N 5. 535–553.
- Hales T. Cannonballs and honeycombs // Notices of the American Mathematical Society. 2000. 47, N 4. 440–449.
- Stoyan Y., Yaskov G. Packing identical spheres into a rectangular parallelepiped // Intelligent Decision Support. Wiesbaden: Betriebswirtschaftlicher Verlag Dr. Th. Gabler, 2008. 47–67.
- Stoyan Yu.G., Yaskov G. Packing identical spheres into a cylinder // International Transactions in Operational Research. 2009. 17, N 1. 51–70.
- 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.
- 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.
- Fu L., Steinhardt W., Zhaod H., Socolar J.E.S., Charbonneau P. Hard sphere packings within cylinders // Soft Matter. 2016. 12. 2505–2514.
- 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.
- Stoyan Yu.G., Scheithauer G., Yaskov G.N. Packing unequal spheres into various containers // Cybernetics and Systems Analysis. 2016. 52, N 3. 419–426.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. 50–57.
- Бухаров Д.С., Казаков А.Л. Программная система “ВИГОЛТ” для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование. 2012. 13 65–74.
- Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. 87–100.
- 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.
- Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Вычислительные методы и программирование. 2015. 16. 307–317.
- Казаков А.Л., Лемперт A.A., Нгуен Г.Л. Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой // Вычислительные методы и программирование. 2016. 17. 177–188.
- 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.
- 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.
- Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989.
- 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.
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
Section
Section 1. Numerical methods and applications