Geodesic
Algorithms for constructing optimal covering of planar figures with disks sets of linearly different radii
The Bulletin of Irkutsk State University. Series Mathematics, Tome 46 (2023), pp. 35-50 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of optimal covering of plane figures with sets of a fixed number of different circles is considered. We suppose that each circle has a radius equal to the sum of the parameter common to all and its individual number. The main aim of the paper is to develop algorithms that allow the construction of a covering with a minimum common parameter. It is proved that the problem can be reduced to minimizing a function of several variables depending on the coordinates of the centers of the circles. The zones of influence of points serving as the centers of circles for a fixed set of individual numbers have been studied. Iterative algorithm for solving the problem is proposed using the concepts of the Chebyshev center and a generalization of the Dirichlet zone. The possibilities of applying the results of the article to the construction of sensor networks are shown.
Keywords: disks coverage, Dirichlet zone, Chebyshev center, minimization.
Mots-clés : domain of dominance 
@article{IIGUM_2023_46_a2,
     author = {Pavel D. Lebedev and Krasimir L. Stoychin},
     title = {Algorithms for constructing optimal covering of planar figures with disks sets of linearly different radii},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {35--50},
     year = {2023},
     volume = {46},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2023_46_a2/}
}
TY  - JOUR
AU  - Pavel D. Lebedev
AU  - Krasimir L. Stoychin
TI  - Algorithms for constructing optimal covering of planar figures with disks sets of linearly different radii
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2023
SP  - 35
EP  - 50
VL  - 46
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2023_46_a2/
LA  - ru
ID  - IIGUM_2023_46_a2
ER  - 
%0 Journal Article
%A Pavel D. Lebedev
%A Krasimir L. Stoychin
%T Algorithms for constructing optimal covering of planar figures with disks sets of linearly different radii
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2023
%P 35-50
%V 46
%U http://geodesic.mathdoc.fr/item/IIGUM_2023_46_a2/
%G ru
%F IIGUM_2023_46_a2
Pavel D. Lebedev; Krasimir L. Stoychin. Algorithms for constructing optimal covering of planar figures with disks sets of linearly different radii. The Bulletin of Irkutsk State University. Series Mathematics, Tome 46 (2023), pp. 35-50. http://geodesic.mathdoc.fr/item/IIGUM_2023_46_a2/

[1] Astrakov S.N., Erzin A.I., Zalyubovskiy V.V., “Sensor networks and covering of plane by discs”, Diskretn. Anal. Issled. Oper., 16:3 (2009), 3–19 (in Russian) | MR | Zbl

[2] Astrakov S.N., Kvashnin A.G., Korolenko L.A., “Constructing efficient sensor networks, taking into account the cost”, Mathematical Structures and Modeling, no. 3:43 (2017), 50–62 (in Russian) | MR

[3] Brusov V.S., Piyavskii S.A., “A computational algorithm for optimally covering a plane region”, Comput. Math. Math. Phys., 11:2 (1971), 17–27 (in Russian) | DOI

[4] Galiev Sh.I., Khorkov A.V., “Multiple circle coverings of an equilateral triangle, square, and circle”, Diskretn. Anal. Issled. Oper., 22:6 (2015), 5–28 | DOI | MR | Zbl

[5] Garkavi A.L., “On the Chebyshev center and convex hull of a set”, Uspekhi Mat. Nauk, 9:6(120) (1964), 139–145 (in Russian) | MR | Zbl

[6] Kazakov A.L., Lebedev P.D., Lempert A.A., “On covering bounded sets by collections of circles of various radii”, The Bulletin of Irkutsk State University. Series Mathematics, 31 (2020), 18–33 | DOI | MR | Zbl

[7] Conway J.H., Sloane N.J.A., Sphere Packings, Lattices and Groups, Springer Science Business Media, 2013, 682 pp. | DOI | MR | MR

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

[9] Lebedev P.D., Kazakov A.L., “Iterative algorithms for constructing the thinnest coverings of convex polyhedra by sets of different balls”, Trudy Inst. Mat. i Mekh. UrO RAN, 27, no. 1, 2021, 116–129 (in Russian) | DOI | DOI | MR

[10] Lebedev P.D., Kuvshinov O.A., “Algorithms for constructing suboptimal coverings of plane figures with disks in the class of regular lattices”, Izv. IMI UdGU, 61 (2023), 76–93 (in Russian) | DOI | MR | Zbl

[11] Miklush V.A., Tatarnikova T.M., “Problem solution of different sensors location in organizing a mesh topology wireless sensor network”, Journal Achievements of Modern Radioelectronics, 76:12 (2022), 15–20 (in Russian) | DOI

[12] Petunin A.A., Chentsov A.G., Chentsov P.A., “About routing in the sheet cutting”, Vestnik YuUrGU. Ser. Mat. Model. Progr., 10:3 (2017), 25–39 (in Russian) | DOI | Zbl

[13] Sosov E.N., “Metric Space of All $N$-nets of a Geodesic Space”, Kazan. Gos. Univ. Uchen. Zap. Ser. Fiz.-Mat. Nauki, 151, no. 4, 2009, 136–149 (in Russian)

[14] Takhonov I.I., “On some problems of covering the plane with circles”, Diskretn. Anal. Issled. Oper., 21:1 (115) (2014), 84–102 (in Russian) | MR | Zbl

[15] Chen K., Giblin P.J., Irving A., Mathematical explorations with MATLAB, Cambridge University Press, Cambridge, 1999, 306 pp. https://archive.org/details/mathematicalexpl0000chen | MR | Zbl

[16] Kazakov A. L., Lempert A. A., “On Mathematical Models for Optimization Problem of Logistics Infrastructure”, Intern. J. of Artificial Intelligence, 13:1 (2015), 200–210 http://www.ceser.in/ceserp/index.php/ijai/article/view/3537

[17] Kazakov A., Lempert A., Le Q. M., “On the thinnest covering of fixed size containers with non-Euclidean metric by incongruent circles”, Communications in Computer and Information Science, 1090 (2019), 195–206 | DOI | MR

[18] Kazakov A., Lempert A., Le Q. M., “On Multiple Coverings of Fixed Size Containers with Non-Euclidean Metric by Circles of Two Types”, Communications in Computer and Information Science, 1275 (2020), 120–132 | DOI | MR | Zbl

[19] Lempert A., Kazakov A., Le Q. Mung, “On reserve and double covering problems for the sets with non-Euclidean metrics”, Yugoslav Journal of Operations Research, 21:1 (2019) | DOI | MR

[20] Tóth F. G., “Covering the plane with two kinds of circles”, Discrete Computational Geometry, 13:3–4 (1995), 445–457 | DOI | MR