рус eng
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

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
  1. 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)
  2. 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)
  3. 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)
  4. 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
  5. 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)
  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, 2020, vol. 31, pp. 18–33. https://doi.org/10.26516/1997-7670.2020.31.18
  7. 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
  8. 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)
  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, 2021, vol. 27, no. 1, pp. 116–129. https://doi.org/10.21538/0134-4889-2021-27-1-116-129 (in Russian)
  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, 2023, vol. 61, pp. 76–93. https://doi.org/10.35634/2226-3594-2023-61-05 (in Russian)
  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, 2022, vol. 76, no. 12, pp. 15–20.https://doi.org/10.18127/j20700784-202212-03 (in Russian)
  12. 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)
  13. 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).
  14. 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)
  15. 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
  16. 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
  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, 2019, vol. 1090, pp. 195–206.https://doi.org/10.1007/978-3-030-33394-2_15
  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, 2020, vol. 1275, pp. 120–132. https://doi.org/10.1007/978-3-030-58657-7_12
  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, 2019, vol. 21, no 1. https://doi.org/10.2298/YJOR171112010L
  20. 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

Full text (russian)