This paper is devoted to the problem of constructing an optimal covering of a two-dimensional figure by the union of circles. The radii of the circles, generally speaking, are different. Each of them is equal to the product of some positive coefficient and the parameter r common to all circles, which is the objective function to be minimized. We carried out an analytical study of the problem and obtained expressions that allow us to describe the generalized Dirichlet zones for the considered case. We propose an iterative procedure correcting the coordinates of the circles’ centers that form the covering, which is based on finding the Chebyshev centers of the generalized Dirichlet zones. This procedure does not impair the properties of the covering. A computational algorithm is proposed and implemented. It includes the multistart method to generate the initial positions of points and the iterative procedure. We carried out a computational experiment to find optimal coverings by sets of circles at various coefficients that determine the radius of each of them. Two and three different types of circles are used. Both convex and nonconvex polygons are taken as the covered sets. The analysis of the calculation results was carried out, which allowed us to draw conclusions about the properties of the constructed coverings.

Alexander Kazakov, Dr. Sci. (Phys.–Math.), Prof., Matrosov Institute for System Dynamics and Control Theory SB RAS, 134, Lermontov str., Irkutsk, 664033, Russian Federation; Irkutsk National Research Technical University, 83, Lermontov str., Irkutsk, Russian Federation, tel.: (3952)453033, e-mail: kazakov@icc.ru

Pavel Lebedev, Cand. Sci. (Phys.–Math.), Krasovskii Institute of Mathematics and Mechanics of UB RAS, 16, Kovalevskaya str., Yekaterinburg, 620108, Russian Federation, tel.: (343)3753489, e-mail: pleb@yandex.ru

Anna Lempert, Cand. Sci. (Phys.–Math.), Matrosov Institute for System Dynamics and Control Theory SB RAS, 134, Lermontov str., Irkutsk, 664033, Russian Federation, tel.: (3952)453030, e-mail: lempert@icc.ru

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

1. Banhelyi B., Palatinus E., Levai B.L. Optimal circle covering problems and their applications. Cent. Eur. J. Oper. Res., 2015, vol. 23, no. 4, pp. 815-832. https://doi.org/10.1007/s10100-014-0362-7

2. Bychkov I.V., Kazakov A.L., Lempert A.A., Bukharov D.S., Stolbov A.B. An intelligent management system for the development of a regional transport logistics infrastructure. Autom. Remote Control, 2016, vol. 77, no. 2, pp. 332-343. https://doi.org/10.1134/S0005117916020090

3. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles. Anal. Geom. Metr. Spaces, 2017, vol. 5, no. 1, pp. 40-46. https://doi.org/10.1515/agms-2017-0002

4. Florian A., Heppes A. Solid Coverings of the Euclidean Plane with Incongruent Circles. Discrete Comput. Geom., 2000. vol. 23, iss. 2, pp. 225-245. https://doi.org/10.1007/PL00009497

5. Kazakov A.L., Lebedev P.D. Algorithms for constructing optimal n-networks in metric spaces. Autom. Remote Control, 2017, vol. 78, no. 7, pp. 1290-1301. https://doi.org/10.1134/S0005117917070104

6. Lempert A.A., Kazakov A.L., Bukharov D.S. Mathematical model and program system for solving a problem of logistic objects placement. Autom. Remote Control, 2015, vol. 76, no. 8. pp. 1463-1470. https://doi.org/10.1134/S0005117915080111

7. Lempert A., Kazakov A., Le Q.M. On reserve and double covering problems for the sets with non-Euclidean metrics. Yugoslav J. Oper. Research, 2019, vol. 29, no. 1. pp. 69-79. https://doi.org/10.2298/YJOR171112010L

8. Preparata F.P., Shamos M.I. Computational Geometry: An Introduction. NY, Springer-Verlag Publ., 1985, 396 p.

9. Toth L.F. Regular figures. NY, A Pergamon Press Book Publ., 1964, 339 p.

10. Toth L.F. Solid circle-packings and circle-coverings. Studia Sci. Math. Hungar., 1968, vol. 3, pp. 401-409.

11. Toth F.G. Covering the plane with two kinds of circles. Discrete Comput. Geom., 1995, vol. 13, iss. 3-4. pp. 445-457. https://doi.org/10.1007/BF02574055