List of issues > Series «Mathematics». 2023. Vol 46
Algorithms for Constructing Optimal Covering of Planar
Figures with Disks Sets of Linearly Different Radii
Author(s)
Pavel D. Lebedev1,2
,
Krasimir L. Stoychin1


1Ural Federal University named after B. N. Yeltsin, Yekaterinburg, Russian Federation
2N. N. Krasovskii Institute of Mathematics and Mechanics UB RAS, Yekaterinburg, Russian Federation
Abstract
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.
About the Authors
Pavel D. Lebedev, Cand. Sci. (Phys.Math.), Senior Researcher, Institute of Mathematics and Mechanics UB RAS, Yekaterinburg, 620108, Russian Federation, Ural Federal University named after B. N. Yeltsin, Yekaterinburg, 620002, Russian Federation, pleb@yandex.ru
Krasimir L. Stoychin, Postgraduate, Ural Federal University named after B. N. Yeltsin, Yekaterinburg, 620002, Russian Federation, k001kk96@mail.ru
For citation
Lebedev P. D., Stoychin K. L. Algorithms for Constructing Optimal Covering of Planar Figures with Disks Sets of Linearly Different Radii. The Bulletin of Irkutsk
State University. Series Mathematics, 2023, vol. 46, pp. 35–50. (in Russian)
https://doi.org/10.26516/1997-7670.2023.46.35
Keywords
disks coverage, domain of dominance, Dirichlet zone, Chebyshev center,
minimization
UDC
514.174.3
MSC
41A50, 52C15
DOI
https://doi.org/10.26516/1997-7670.2023.46.35
References
- Astrakov S.N., Erzin A.I., Zalyubovskiy V.V. Sensor networks and covering of plane by discs. Diskretn. Anal. Issled. Oper., 2009, vol. 16, no. 3, pp. 3–19. https://www.mathnet.ru/eng/da/v16/i3/p3 (in Russian)
- Astrakov S.N., Kvashnin A.G., Korolenko L.A. Constructing efficient sensor networks, taking into account the cost. Mathematical Structures and Modeling, 2017, no. 3(43), pp. 50–62. (in Russian)
- Brusov V.S., Piyavskii S.A. A computational algorithm for optimally covering a plane region. Comput. Math. Math. Phys., 1971, vol. 11, no. 2, pp. 17—27.https://doi.org/10.1016/0041-5553(71)90161-3 (in Russian)
- Galiev Sh.I., Khorkov A.V. Multiple circle coverings of an equilateral triangle, square, and circle. Diskretn. Anal. Issled. Oper., 2015, vol. 22, no. 6, pp. 5–28.https://doi.org/10.17377/daio.2015.22.482
- Garkavi A.L. On the Chebyshev center and convex hull of a set. Uspekhi Mat. Nauk, 1964, vol. 19, no. 6(120), pp. 139–145. https://www.mathnet.ru/eng/rm/v19/i6/p139 (in Russian)
- 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, 2020, vol. 31, pp. 18–33. https://doi.org/10.26516/1997-7670.2020.31.18
- Conway J.H., Sloane N.J.A. Sphere Packings, Lattices and Groups. Springer Science & Business Media, 2013, 682 p.https://doi.org/10.1007/978-1-4757-2016-7
- Lebedev P.D. Iterative methods for approximations constructing of optimal covering for nonconvex plane sets. Chelyabinsk Phys-Math Journal, 2019, vol. 4, no 1, pp. 5–17. https://doi.org/10.24411/2500-0101-2019-14101 (in Russian)
- 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, 2021, vol. 27, no. 1, pp. 116–129. https://doi.org/10.21538/0134-4889-2021-27-1-116-129 (in Russian)
- 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, 2023, vol. 61, pp. 76–93. https://doi.org/10.35634/2226-3594-2023-61-05 (in Russian)
- 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, 2022, vol. 76, no. 12, pp. 15–20.https://doi.org/10.18127/j20700784-202212-03 (in Russian)
- Petunin A.A., Chentsov A.G., Chentsov P.A. About routing in the sheet cutting. Vestnik YuUrGU. Ser. Mat. Model. Progr., 2017, vol. 10, no. 3, pp. 25–39.https://doi.org/10.14529/mmp170303 (in Russian)
- Sosov E.N. Metric Space of All 𝑁-nets of a Geodesic Space. Kazan. Gos. Univ. Uchen. Zap. Ser. Fiz.-Mat. Nauki, 2009, vol. 151, no. 4, pp. 136–149. Available at: https://www.mathnet.ru/eng/uzku/v151/i4/p136 (in Russian).
- Takhonov I.I. On some problems of covering the plane with circles. Diskretn. Anal. Issled. Oper., 2014, vol. 21, no. 1 (115). pp. 84–102. https://www.mathnet.ru/eng/da/v21/i1/p84 (in Russian)
- Chen K., Giblin P.J., Irving A. Mathematical explorations with MATLAB. Cambridge [England], Cambridge University Press, 1999, 306 p. Available at: https://archive.org/details/ mathematicalexpl0000chen
- Kazakov A.L., Lempert A.A. On Mathematical Models for Optimization Problem of Logistics Infrastructure. Intern. J. of Artificial Intelligence, 2015, vol. 13, no 1, pp. 200–210.http://www.ceser.in/ceserp/index.php/ijai/article/view/3537
- 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, 2019, vol. 1090, pp. 195–206.https://doi.org/10.1007/978-3-030-33394-2_15
- 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, 2020, vol. 1275, pp. 120–132. https://doi.org/10.1007/978-3-030-58657-7_12
- 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, 2019, vol. 21, no 1. https://doi.org/10.2298/YJOR171112010L
- T´oth F.G. Covering the plane with two kinds of circles. Discrete & Computational Geometry, 1995, vol. 13, iss. 3–4, pp. 445–457.https://doi.org/10.1007/BF02574055