On the densest packing of equal spheres into a three -dimensional convex set
Các tác giả
Từ khóa:
packing equal spheres, optimal packing of spheres, optical - geometric approach, billiard simulation, three - dimensional spaceTóm tắt
Packing problems are classic problem of mathematical optimization and are very interesting NP - hard optimization problems with a wide variety of applications. That is, no procedure is able to exactly solve them in deterministic polynomial time. In this paper, we focus on problems dealing with circular objects, being three - dimensional. A special algorithm based on the optical - geometric approach for solving the problem is suggested. We also present illustrative numerical results using our algorithm both in three - dimensional Euclidean and non - Euclidean spaces.
Abstract
Packing problems are classic problem of mathematical optimization and are very interesting NP - hard optimization problems with a wide variety of applications. That is, no procedure is able to exactly solve them in deterministic polynomial time. In this paper, we focus on problems dealing with circular objects, being three - dimensional. A special algorithm based on the optical - geometric approach for solving the problem is suggested. We also present illustrative numerical results using our algorithm both in three - dimensional Euclidean and non - Euclidean spaces.
Tài liệu tham khảo
[1] I. Castillo, F. J. Kampas, J. D. Pinter, “Solving circle packing problems by global opti-mization: Numerical results and industrial applications”, uropean Journal of Operational Research, vol. 191, iss. 3, 2008, pp.786 – 802.
[2] J. A. George, J. M. George and B. W. Lamar, “Packing different – sized circles into a rectangular container”, European Journal of Operational Research, vol.84, 1995, pp. 693 – 712.
[3] J. A. George, “Multiple container packing: a case study of pipe packing”, Journal of the Operational Research Society, vol. 47, 1996, pp. 1098 – 1109.
[4] F. Harary, W. Randolph, P. G. Mezey, “A study of maximum unit-circle caterpillars — tools for the study of the shape of adsorption patterns”, Discrete Applied Mathematics, vol. 67, iss. 1 – 3, 1996, pp. 127 – 135.
[5] J. Wang, “Packing of Unequal Spheres and Automated Radiosurgical Treatment Planning”, Journal of Combinatorial Opti-mization, vol. 3, 1999, pp. 453 – 463.
[6] P. Szabo, M. Markot, T. Csendes, E. Specht, and L. Casado, “New approaches to circle packing in square with program codes,” in Springer US, New York, 2007.
[7] A. L. Kazakov, A. A. Lempert and D. S. Bukharov, “On segmenting logistical zones for servicing continuously developed consumers”, in Automation and Remote Control, vol. 74 (6), 2013, pp. 968 – 977.
[8] A. L. Kazakov and A. A. Lempert, “On mathematical models for optimization problem of logistics infrastructure”, in International Journal of Artificial Intelligence, vol. 13 (1), 2015, pp. 200 – 210.
[9] Y. Stoyan, “Mathematical methods for geometric design”, in Advances in CAD/CAM//. Proceeding PROLAMAT82. Leningrad, USSR, 1982, pp. 67 – 86. Amsterdam: North-Holland. [10] E. Specht, “Packomania”. Internet: http://www.packomania.com, 2010.
[11] K.J.Nurmela and P.R.J. Ostergard , “Packing up to 50 equal circles in a square”, in Discrete and Computational Geometry, vol. 18, 1997, pp. 111 – 120.
[12] M.Cs. Markot and T.A. Csendes, “A new verified optimization technique for the packing circles in a unit square problems”, In SIAM Journal on Optimization, vol. 16, 2005, pp. 193 – 219.
[13] F. Fodor, “The densest packing of 19 congruent circles in a circle”, in Contributions to Algebra and Geometry, vol. 74 (2), 1999, pp. 139 – 145.
[14] F. Fodor, “The densest packing of 12 congruent circles in a circle”, in Contributions to Algebra and Geometry, vol. 43, 2000, pp. 401 – 409.
[15] F. Fodor, “The densest packing of 13 congruent circles in a circle”, in Contributions to Algebra and Geometry, vol. 40 (2), 2003, pp. 431 – 440.
[16] A. Grosso, A. R. M. J. U. Jamali and M. Locatelli, “Solving the problem of packing equal and unequal circles in a circular container”, Journal of Global Optimization, vol. 47, 2010, pp. 63 – 81.
[17] P. Szabo and E. Specht, “Packing up to 200 equal circles in a square.models and algorithms for global optimization”, Optimization and Its Applications, vol. 4, 2007, pp. 141 – 156.
[18] R. L. Graham, B. D. Lubachevsky, K. J. Nurmela and P. R. J. Ostergard, “Dense packings of congruent circles in a circle”, in Discrete Mathematics, vol. 181, 1998, pp. 139 – 154.
[19] E. G. Birgin and F. N. C. Sobral, “Minimizing the object dimensions in circle and sphere packing problems”, Computers and Operations Research, vol. 35, 2008, pp. 2357 – 2375.
[20] M. Hifi and R. M'Hallah, “Approximate algorithms for constrained circular cutting problems”, Computers and Operations Re-search, vol. 31 (5), 2004, pp. 675 – 694.
[21] S. I. Galiev and M. S. Lisafina, “Linear models for the approximate solution of the problem of packing equal circles into a given domain”, European Journal of Operational Research, Elsevier, vol. 230 (3), 2013, pp.505 – 514.
[22] Y. Stoyan and G. Yaskov, “Packing Identical Spheres into a Rectangular Parallelepiped”, in Intelligent Decision Support, Gabler, 2008, pp.47 – 67.
[23] Y. G. Stoyan and G. Yaskov, “Packing identical spheres into a cylinder”, Interna-tional Transactions in Operational Research, vol. 17, 2009, pp. 51 – 70.
[24] T. Gensane, “Dense packing of equal spheres in a cube”, the Electronic Journal of Combinatorics, vol. 11, 2004, pp. 1 – 17.
[25] M. Tatarevic, “On limits of dense pac-king of equal spheres in a cube”, CoRR,abs/1503.07933, 2015, Internet: http://arxiv.org/abs/1503.07933.
[26] R. M'Hallah and A. Alkandari, “Packing Unit Spheres into a Cube Using VNS”, Electronic Notes in Discrete Mathematics, vol. 39, 2012, pp. 201 – 208.
[27] A. L. Kazakov and A. A. Lempert, “An approach to optimization in transport logis-tics”, in Automation and Remote Control, vol. 72(7), 2011, pp. 50 – 57.
[28] A. L. Kazakov, A. A. Lempert and T. T. Thanh, “The sphere packing problem into bounded containers in three - dimension non - Euclidean space”, in IFAC – Papers On Line, vol. 51(32), 2018, pp. 782 – 787.
[29] A. L. Kazakov, A. A. Lempert and N. H. Liem, “The problem of the optimal packing of the equal circles for special non - euclidean metric”, Communications in Computer and Information Science, vol. 661, 2017, pp. 25 – 68.
[30] F. Preparata and M. Shamos, Compu-tational Geometry: An Introduction. New York: Springer – Verlag, Berlin, Heidelberg, 1985.
[31] H. Pfoertner, “Densest packings of n equal spheres in a sphere of radius 1”, 2008, Internet: www.randomwalk.de/sphere/insphr/spisbest.txt
Tải xuống
Tải xuống: 15
