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

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

Authors

  • A.L. Kazakov
  • A.A. Lempert
  • C.T. Ta

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.

New computational technologies

Downloads

Published

2020-05-20

Issue

Vol. 21 (2020): Issue 2.

Section

Section 1. Numerical methods and applications

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. I. Castillo, F. J. Kampas, and J. D. Pintér, “Solving Circle Packing Problems by Global Optimization: Numerical Results and Industrial Applications ,” Eur. J. Oper. Res. 191 (3), 786-802 (2008).
  2. F. Harary, W. Randolph, and P. G. Mezey, “A Study of Maximum Unit-Circle Caterpillars - Tools for the Study of the Shape of Adsorption Patterns,” Discrete Appl. Math. 67 (1-3), 127-135 (1996).
  3. J. Wang, “Packing of Unequal Spheres and Automated Radiosurgical Treatment Planning,” J. Comb. Optim. 3, 453-463 (1999).
  4. N. Chernov, Yu. Stoyan, and T. Romanova, “Mathematical Model and Efficient Algorithms for Object Packing Problem,” Comput. Geom. 43 (5), 535-553 (2010).
  5. T. C. Hales, “Cannonballs and Honeycombs,” Not. Am. Math. Soc. 47 (4), 440-449 (2000).
  6. Y. Stoyan and G. Yaskov, “Packing Identical Spheres into a Rectangular Parallelepiped,” in Intelligent Decision Support (Betriebswirtschaftlicher Verlag Dr. Th. Gabler, Wiesbaden, 2008), pp. 47-67.
  7. Yu. G. Stoyan and G. N. Yaskov, “Packing Identical Spheres into a Cylinder,” Int. Trans. Oper. Res. 17 (1), 51-70 (2010).
  8. W. Huang and L. Yu, Serial Symmetrical Relocation Algorithm for the Equal Sphere Packing Problem arXiv preprint: 1202.4149v1 [cs.DM] (Cornell Univ. Library, Ithaca, 2012),
    available at
    https://arxiv.org/abs/1202.4149.
  9. A. Mughal, H. K. Chan, D. Weaire, and S. Hutzler, “Dense Packings of Spheres in Cylinders: Simulations,” Phys. Rev. E 85 (2012).
    doi 10.1103/PhysRevE.85.051305
  10. L. Fu, W. Steinhardt, H. Zhao, et al., “Hard Sphere Packings within Cylinders,” Soft Matter. 12, 2505-2514 (2016).
  11. G. Scheithauer, Yu. Stoyan, and G. Yaskov, “Packing Non-Equal Spheres into Containers of Different Shapes,” (2013).
    |
    http://www.math.tu-dresden.de/ scheith/ABSTRACTS/2013-spheres.html|. Cited March 25, 2020.
  12. Yu. G. Stoyan, G. Scheithauer, and G. N. Yaskov, “Packing Unequal Spheres into Various Containers,” Cybern. Syst. Anal. 52 (3), 419-426 (2016).
  13. O. M. Khlud and G. N. Yaskov, “Packing Homothetic Spheroids into a Larger Spheroid with the Jump Algorithm,” Contr. Navig. Commun. Syst. 6 (46), 131-135 (2017).
  14. T. Kubach, A. Bortfeldt, T. Tilli, and H. Gehring, 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 . Cited March 25, 2020.
  15. T. Kubach, A. Bortfeldt, T. Tilli, and H. Gehring, “Greedy Algorithms for Packing Unequal Spheres into a Cuboidal Strip or a Cuboid,” Asia Pac. J. Oper. Res. 28 (6), 739-753 (2011).
  16. W. Q. Huang, Y. Li, H. Akeb, and C. M. Li, “Greedy Algorithms for Packing Unequal Circles into a Rectangular Container,” J. Oper. Res. Soc. 56 (5), 539-548 (2005).
  17. M. Hifi and L. Yousef, “Width Beam and Hill-Climbing Strategies for the Three-Dimensional Sphere Packing Problem,” in 2014 Federated Conf. on Computer Science and Information Systems, Warsaw, Poland, September 7-10, 2014 (IEEE Press, New York, 2014), pp. 421-428.
  18. S. Yamada, J. Kanno, and M. Miyauchi, “Multi-Sized Sphere Packing in Containers: Optimization Formula for Obtaining the Highest Density with Two Different Sized Spheres,” IPSJ Online Trans. 4, 126-133 (2011).
  19. A. L. Kazakov and A. A. Lempert, “An Approach to Optimization in Transport Logistics,” Avtom. Telemekh., No. 7, 50-57 (2011) [Autom. Rem. Contr. 72 (7), 1398-1404 (2011)].
  20. D. S. Bukharov and A. L. Kazakov, “VIGOLT System for Solving Transport Logistics Optimization Problems,” Vychisl. Metody Programm. 13, 65-74 (2012).
  21. A. L. Kazakov, A. A. Lempert, and D. S. Bukharov, “On Segmenting Logistical Zones for Servicing Continuously Developed Consumers,” Avtom. Telemekh., No. 6, 87-100 (2013) [Autom. Rem. Contr. 74 (6), 968-977 (2013)].
  22. A. L. Kazakov and A. A. Lempert, “On Mathematical Models for Optimization Problem of Logistics Infrastructure,” Int. J. Artif. Intell. 13 (1), 200-210 (2015).
  23. A. L. Kazakov and P. D. Lebedev, “Algorithms of Optimal Packing Construction for Planar Compact Sets,” Vychisl. Metody Programm. 16, 307-317 (2015).
  24. A. L. Kazakov, A. A. Lempert, and H. L. Nguyen, “An Algorithm of Packing Congruent Circles in a Multiply Connected Set with Non-Euclidean Metrics,” Vychisl. Metody Programm. 17, 177-188 (2016).
  25. A. L. Kazakov, A. A. Lempert, and T. T. Ta, “The Sphere Packing Problem into Bounded Containers in Three-Dimension Non-Euclidean Space,” IFAC-PapersOnLine 51 (32), 782-787 (2018).
  26. A. L. Kazakov, A. A. Lempert, and T. T. Ta, “On the Algorithm for Equal Balls Packing into a Multi-connected Set,” in Proc. VIth Int. Workshop on Critical Infrastructures: Contingency Management, Intelligent, Agent-Based, Cloud Computing and Cyber Security, Baikalsk, Russia, March 17-24, 2019 (Atlantis Press, Paris, 2019), pp. 216-222.
  27. F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Springer, New York, 1985; Mir, Moscow, 1989).
  28. R. L. Graham, B. D. Lubachevsky, K. J. Nurmela, and P. R. J. Östergard, “Dense Packings of Congruent Circles in a Circle,” Discrete Math. 181 (1-3), 139-154 (1998).