Algorithms of optimal covering of 2D sets with dynamical metrics

P. D. Lebedev ; A. A. Lempert ; A. L. Kazakov

Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 60 (2022), pp. 58-72.

Résumé

The paper deals with the problem of constructing the thinnest covering for a convex set by a set of similar elements. As a distance between two points, we use the shortest time it takes to achieve one point from another, and the boundary of each covering circle is an isochron. Such problems arise in applications, particularly in sonar and underwater surveillance systems. To solve the problems of covering with such circles and balls, we previously proposed algorithms based both on variational principles and geometric methods. The purpose of this article is to construct coverings when the characteristics of the medium change over time. We propose a computational algorithm based on the theory of wave fronts and prove the statement about its properties. Illustrative calculations are performed.

Détail

Keywords: optimal covering, wave front, dynamical metric, Chebyshev center.

Bibliographie

[1] Tóth L. F., Regular figures, Pergamon Press, London, 1964 | MR | Zbl

[2] T{ó}th L. F., “Solid circle-packings and circle-coverings”, Studia Scientiarum Mathematicarum Hungarica, 3 (1968), 401–409 | MR | Zbl

[3] Heppes A., “Covering a planar domain with sets of small diameter”, Periodica Mathematica Hungarica, 53 (2006), 157–168 | DOI | MR | Zbl

[4] Szabó P. G., Specht E., “Packing up to 200 equal circles in a square”, Models and algorithms for global optimization, Springer, New York, 2007, 141–156 | DOI | MR | Zbl

[5] Tóth G. F., “Thinnest covering of a circle by eight, nine, or ten congruent circles”, Combinatorial and Computational Geometry, 52 (2005), 361–376 | MR | Zbl

[6] Takhonov I. I., “On some problems of covering the plane with circles”, Diskretnyi Analiz i Issledovanie Operatsii, 21:1 (2014), 84–102 (in Russian) | MR | Zbl

[7] Dorninger D., “Thinnest covering of the Euclidean plane with incongruent circles”, Analysis and Geometry in Metric Spaces, 5:1 (2017), 40–46 | DOI | MR | Zbl

[8] Specht E., Packomania, , 2022 (visited on 06/10/2022) http://www.packomania.com

[9] Erich's Packing Center, , 2022 (visited on 06/10/2022) https://erich-friedman.github.io/packing/index.html

[10] Conway J. H., Sloane N. J. A., Sphere packings, lattices and groups, Springer, New York, 1988 | DOI | MR | MR | Zbl

[11] Hifi L. M., M'Hallah R., “A literature review on circle and sphere packing problems: models and methodologies”, Advances in Operations Research, 2009 (2009), 150624 | DOI | Zbl

[12] Nurmela K. J., “Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles”, Experimental Mathematics, 9:2 (2000), 241–250 | DOI | MR | Zbl

[13] Galiev S. I., Lisafina M. S., “Linear models for the approximate solution of the problem of packing equal circles into a given domain”, European Journal of Operation Research, 230:3 (2013), 505–514 | DOI | MR | Zbl

[14] Litvinchev I., Ozuna L., “Integer programming formulations for approximate packing circles in a rectangular container”, Mathematical Problems in Engineering, 2014 (2014), 317697 | DOI | MR | Zbl

[15] Stoyan Y. G., Patsuk V. M., “Covering a compact polygonal set by identical circles”, Computational Optimization and Applications, 46:1 (2010), 75–92 | DOI | MR | Zbl

[16] Bánhelyi B., Palatinus E., Lévai B. L., “Optimal circle covering problems and their applications”, Central European Journal of Operations Research, 23:4 (2015), 815–832 | DOI | MR

[17] Pardo E. G., Mladenović N., Pantrigo J. J., Duarte A., “Variable formulation search for the cutwidth minimization problem”, Applied Soft Computing, 13:5 (2013), 2242–2252 | DOI

[18] López C. O., Beasley J. E., “A heuristic for the circle packing problem with a variety of containers”, European Journal of Operational Research, 214:3 (2011), 512–525 | DOI | MR

[19] López C. O., Beasley J. E., “Packing a fixed number of identical circles in a circular container with circular prohibited areas”, Optimization Letters, 13:7 (2019), 1449–1468 | DOI | MR

[20] Huang W., Ye T., “Greedy vacancy search algorithm for packing equal circles in a square”, Operations Research Letters, 38:5 (2010), 378–382 | DOI | MR | Zbl

[21] Graham R. L., Lubachevsky B. D., Nurmela K. J., {Ö}stergård P. R. J., “Dense packings of congruent circles in a circle”, Discrete Mathematics, 181:1–3 (1998), 139–154 | DOI | MR | Zbl

[22] Lubachevsky B. D., “How to simulate billiards and similar systems”, Journal of Computational Physics, 94:2 (1991), 255–283 | DOI | MR | Zbl

[23] Torres–Escobar R., Marmolejo–Saucedo J. A., Litvinchev I., “Binary monkey algorithm for approximate packing non-congruent circles in a rectangular container”, Wireless Networks, 26:7 (2020), 4743–4752 | DOI

[24] Makagonov E. P., “Effective coating of space by coordination spheres — the basic principle of structure and constitution of minerals”, Mineralogiya, 2015, no. 4, 3–18 (in Russian)

[25] Galiev Sh. I., Karpova M. A., “Optimization of multiple covering of a bounded set with circles”, Computational Mathematics and Mathematical Physics, 50:4 (2010), 721–732 | DOI | MR | Zbl

[26] Kazakov A. L., Lempert A. A., “On mathematical models for optimization problem of logistics infrastructure”, International Journal of Artificial Intelligence, 13:1 (2015), 200–210 http://www.ceser.in/ceserp/index.php/ijai/article/view/3537

[27] Erzin A., Lagutkina N., Ioramishvili N., “Barrier covering in 2d using mobile sensors with circular coverage areas”, Learning and intelligent optimization, Springer, Cham, 2020, 342–354 | DOI | MR

[28] Han C., Sun L., Xiao F., Guo J., “An energy efficiency node scheduling model for spatial-temporal coverage optimization in 3d directional sensor networks”, IEEE Access, 4 (2016), 4408–4419 | DOI

[29] Arun D., Pais A. R., “Optimal placement of sensor nodes for water quality measurement”, 2015 Twelfth International Conference on Wireless and Optical Communications Networks (WOCN), 2015 | DOI

[30] Pechenkin V. V., Korolev M. S., “Optimal placement of surveillance devices in a three-dimensional environment for blind zone minimization”, Computer Optics, 41:2 (2017), 245–253 (in Russian) | DOI | MR

[31] Jun S., Chang T.-W., Jeong H., Lee S., “Camera placement in smart cities for maximizing weighted coverage with budget limit”, IEEE Sensors Journal, 17:23 (2017), 7694–7703 | DOI

[32] Wu H., Zhu H., Han X., “An improved $k$-angle coverage algorithm for multimedia wireless sensor networks based on two-layer tabu search”, Peer-to-Peer Networking and Applications, 15:1 (2021), 28–44 | DOI

[33] Kazakov A. L., Lempert A. A., “An approach to optimization in transport logistics”, Automation and Remote Control, 72:7 (2011), 1398–1404 | DOI | MR | Zbl

[34] Keller J. B., Papadakis J. S., Wave propagation and underwater acoustics, Springer, Berlin, 1977 | DOI | MR | Zbl

[35] Orlando D., Ehlers F., “Advances in multistatic sonar”, Sonar systems, IntechOpen, London, 2011 | DOI

[36] Fishchenko V. K., Zimin P. S., Zatserkovnyi A. V., Goncharova A. A., Subote A. E., Golik A. V., “Stationary underwater video observation systems: opportunities for Peter the Great Bay (the Sea of Japan) coastal zone biodiversity state monitoring”, Vestnik of the Far East Branch of the Russian Academy of Sciences, 2018, no. 1, 149–160 (in Russian)

[37] Kazakov A. L., Lempert A. A., Nguyen H. L., “Algorithm for the equal circles optimal covering problem for non-convex polygons with non-Euclidean metric”, Proceedings of Irkutsk State Technical University, 2016, no. 5(112), 45–55 (in Russian) | DOI

[38] Lempert A. A., Le Q. M., “Multiple covering of a closed set on a plane with non-Euclidean metrics”, IFAC-PapersOnLine, 51:32 (2018), 850–854 | DOI

[39] Lempert A. A., Kazakov A. L., Le Q. M., “On reserve and double covering problems for the sets with non-Euclidean metrics”, Yugoslav Journal of Operations Research, 29:1 (2019), 69–79 | DOI | MR | Zbl

[40] Kazakov A. L., Lempert A. A., Ta T. T., “The sphere packing problem into bounded containers in three-dimension non-Euclidean space”, IFAC-PapersOnLine, 51:32 (2018), 782–787 | DOI

[41] Lebedev P. D., Kazakov A. L., “Construction of optimal covers by disks of different radii for convex planar sets”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 25, no. 2, 2019, 137–148 (in Russian) | DOI

[42] Lebedev P. D., “Iterative methods for approximations constructing of optimal covering for nonconvex plane sets”, Chelyabinsk Physical and Mathematical Journal, 4:1 (2019), 5–17 (in Russian) | DOI | Zbl

[43] Preparata F. P., Shamos M. I., Computational geometry: An introduction, Springer, New York, 1985 | DOI | MR

[44] Kazakov A. L., Lebedev P. D., “Algorithms for constructing optimal $n$-networks in metric spaces”, Automation and Remote Control, 78:7 (2017), 1290–1301 | DOI | MR | Zbl

[45] Lebedev P. D., Program for calculating the optimal hemisphere coverage by a set of spherical segments, Registered Rospatent Certificate No 2015661543 dated 10.29.2015