Abstract
The optimal packing problem of equal circles (2-D spheres) in a bounded set P in a two-dimensional metric space is considered. The sphere packing problem is to find an arrangement in which the spheres fill as large proportion of the space as possible. In the case where the space is Euclidean this problem is well known, but the case of non-Euclidean metrics is studied much worse. However there are some applied problems, which lead us to use other special non-Euclidean metrics. For instance such statements appear in the logistics when we need to locate a given number of commercial facilities and to maximize the overall service area. Notice, that we consider the optimal packing problem in the case, where P is a multiply-connected domain. The special algorithm based on optical-geometric approach is suggested and implemented. The results of numerical experiment are presented and discussed.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Conway, J., Sloane, N.: Sphere Packing, Lattices and Groups. Springer Science and Business Media, New York (1999)
Szabo, P., Specht, E.: Packing up to 200 equal circles in a square. In: Torn, A., Zilinskas, J. (eds.) Models and Algorithms for Global Optimization. Optimization and Its Applications, vol. 4, pp. 141–156. Springer, Heidelberg (2007)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)
Levenshtein, V.: On bounds for packing in n-dimensional Euclidean space. Sov. Math. Dokl. 20(2), 417–421 (1979)
Garey, M., Johnson, D.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Casado, L., Garcia, I., Szabo, P., Csendes, T.: Packing equal circles in a square ii. New results for up to 100 circles using the tamsass-pecs algorithm. In: Giannessi, F., Pardalos, P., Rapcsac, T. (eds.) Optimization Theory: Recent Developments from Matrahaza, vol. 59, pp. 207–224. Kluwer Academic Publishers, Dordrecht (2001)
Markot, M., Csendes, T.: A new verified optimization technique for the “packing circles in a unit square” problems. SIAM J. Optim. 16(1), 193–219 (2005)
Goldberg, M.: Packing of 14, 16, 17 and 20 circles in a circle. Math. Mag. 44(3), 134–139 (1971)
Graham, R., Lubachevsky, B., Nurmela, K., Ostergard, P.: Dense packings of congruent circles in a circle. Discrete Math. 181(1–3), 139–154 (1998)
Lubachevsky, B., Graham, R.: Curved hexagonal packings of equal disks in a circle. Discrete Comput. Geom. 18, 179–194 (1997)
Birgin, E., Gentil, J.: New and improved results for packing identical unitary radius circles within triangles, rectangles and strips. Comput. Oper. Res. 37(7), 1318–1327 (2010)
Galiev, S., Lisafina, M.: Linear models for the approximate solution of the problem of packing equal circles into a given domain. Eur. J. Oper. Res. 230(3), 505–514 (2013)
Litvinchev, I., Ozuna, E.: Packing circles in a rectangular container. In: Proceedings of the International Congress on Logistics and Supply Chain, pp. 24–25 (2013)
Litvinchev, I., Ozuna, E.: Integer programming formulations for approximate packing circles in a rectangular container. Math. Probl. Eng. (2014)
Lopez, C., Beasley, J.: A heuristic for the circle packing problem with a variety of containers. Eur. J. Oper. Res. 214, 512–525 (2011)
Lopez, C., Beasley, J.: Packing unequal circles using formulation space search. Comput. Oper. Res. 40, 1276–1288 (2013)
Pedroso, J., Cunha, S., Tavares, J.: Recursive circle packing problems. Int. Trans. Oper. Res. 23(1), 355–368 (2014)
Andrade, R., Birgin, E.: Symmetry-breaking constraints for packing identical rectangles within polyhedra. Optim. Lett. 7(2), 375–405 (2013)
Lempert, A., Kazakov, A.: On mathematical models for optimization problem of logistics infrastructure. Int. J. Artif. Intell. 13(1), 200–210 (2015)
Coxeter, H.S.M.: Arrangements of equal spheres in non-Euclidean spaces. Acta Math. Acad. Scientiarum Hung. 5(3), 263–274 (1954)
Boroczky, K.: Packing of spheres in spaces of constant curvature. Acta Math. Acad. Scientiarum Hung. 32(3), 243–261 (1978)
Szirmai, J.: The optimal ball and horoball packings of the coxeter tilings in the hyperbolic 3-space. Beitr. Algebra Geom. 46(2), 545–558 (2005)
Szirmai, J.: The optimal ball and horoball packings to the coxeter honeycombs in the hyperbolic d-space. Beitr. Algebra Geom. 48(1), 35–47 (2007)
Szirmai, J.: A candidate for the densest packing with equal balls in thurston geometries. Beitr. Algebra Geom. 55(2), 441–452 (2014)
Preparata, F., Shamos, M.: Computational Geometry. An Introduction. Springer, New York (1985)
Lempert, A., Kazakov, A., Bukharov, D.: Mathematical model and program system for solving a problem of logistic object placement. Autom. Remote Control 76(8), 1463–1470 (2015)
Kazakov, A., Lempert, A., Bukharov, D.: On segmenting logistical zones for servicing continuously developed consumers. Autom. Remote Control 74(6), 968–977 (2013)
Kazakov, A., Lempert, A.: An approach to optimization in transport logistics. Autom. Remote Control 72(7), 1398–1404 (2011)
Specht, E.: Packomania. http://www.packomania.com/. Accessed 28 Oct 2015
Stoyan, Y., Yaskov, G.: Packing congruent spheres into a multi-connected polyhedral domain. Int. Trans. Oper. Res. 20(1), 79–99 (2013)
Acknowledgements
The reported study was particulary funded by RFBR according to the research projects No. 14-07-00222 and No. 16-06-00464.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Kazakov, A.L., Lempert, A.A., Nguyen, H.L. (2017). The Problem of the Optimal Packing of the Equal Circles for Special Non-Euclidean Metric. In: Ignatov, D., et al. Analysis of Images, Social Networks and Texts. AIST 2016. Communications in Computer and Information Science, vol 661. Springer, Cham. https://doi.org/10.1007/978-3-319-52920-2_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-52920-2_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-52919-6
Online ISBN: 978-3-319-52920-2
eBook Packages: Computer ScienceComputer Science (R0)