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

A.A. Lempert

C.T. Ta

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).

Published

20-05-2020

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 (Vychislitel’nye Metody i Programmirovanie). 2020. 21. 152-163. doi 10.26089/NumMet.v21r213

Issue

Section

Section 1. Numerical methods and applications