Artificial intelligence

Abstract: This paper considers the problem of placing spheres in a multidimensional Euclidean space inside a sphere of minimum radius. Such problems arise in geometric optimization and the analysis of high dimensional structures and are applied, in particular, to the construction of multidimensional code configurations in coding and information security. Formally, the problem is reduced to finding a configuration of non overlapping spheres that minimizes the radius of the containing region. This optimization problem belongs to the class of NP hard problems, and its exact solution in high dimensional spaces requires significant computational resources. To obtain fast approximate solutions, a greedy algorithm based on sequential sphere insertion is proposed. At each step, a new sphere is placed as close as possible to the origin while satisfying geometric constraints, whereas previously placed elements remain fixed. This approach ensures low computational complexity and enables the construction of feasible configurations in spaces of large dimensionality. Computational experiments conducted for various dimensions demonstrate the efficiency of the proposed algorithm and allow the density of the resulting configurations to be evaluated. The proposed method can be used as an initial stage prior to applying more sophisticated local or global optimization algorithms.

Keywords: multidimensional sphere, mathematical modeling, computational geometry, greedy algorithm, nonlinear programming

References:

1. J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer New York, NY (1999). doi: 10.1007/978-1-4757-6568-7.
2. S. Li, A. Mirani, M. Karlsson, E. Agrell, Low-Complexity Voronoi Shaping for the Gaussian Channel. IEEE Transactions on Communications 70(2) (2022) 865–873. doi: 10.1109/TCOMM.2021.3130286.
3. M. S. Viazovska, The sphere packing problem in dimension 8. Annals of Mathematics 185(3) (2017) 991–1015. doi: 10.1007/s12652-021-03612-z.
4. H. Cohn, N. Elkies, New upper bounds on sphere packings I. Annals of Mathematics 157(2) (2003) 689–714. doi: 10.4007/annals.2003.157.689.
5. S. Torquato, O. U. Uche, F. H. Stillinger, Random sequential addition of hard spheres in high Euclidean dimensions. Phys. Rev. E 74(6) (2006) 061308. doi: 10.1103/PhysRevE.74.061308.
6. W. S. Jodrey, E. M. Tory, Computer simulation of close random packing of equal spheres. Phys. Rev. A 32(4), (1985) 2347–2351. doi: 10.1103/PhysRevA.32.2347.
7. A. R. Kansal, S. Torquato, F. H. Stillinger, Computer generation of dense polydisperse sphere packings. Journal of Chemical Physics 117 (2002) 8212–8218. doi: 10.1063/1.1511510.
8. G. Yaskov, A. Chugay, Packing equal spheres by means of the block coordinate descent method. CEUR Workshop Proceedings 2608 (2020) 150–160. doi: org/10.32782/cmis/2608-13.
9. M. Skoge, A. Donev, F. H. Stillinger, S. Torquato, Packing hyperspheres in high-dimensional Euclidean spaces Phys. Rev. E 74(4) (2006) 041127. doi: 10.1103/PhysRevE.74.041127.
10. K. He, W. Huang, An efficient placement heuristic for three-dimensional rectangular packing. Computers & Operations Research 38(1) (2011) 227 – 233. doi: 10.1016/j.cor.2010.04.015.
11. D. P. Bertsecal, Nonlinear Programming (1999) ISBN 1-886529-00-0.
12. A. Wächter, L. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program. 106 (2006) 25–57. doi: 10.1007/s10107-004-0559-y.