Geodesic
On covering bounded sets by collections of circles of various radii
The Bulletin of Irkutsk State University. Series Mathematics, Tome 31 (2020), pp. 18-33 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 non-convex 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.
Keywords: optimization, circle covering problem, generalized Dirichlet zone, Chebyshev center, iterative algorithm, computational experiment. 
@article{IIGUM_2020_31_a1,
     author = {A. L. Kazakov and P. D. Lebedev and A. A. Lempert},
     title = {On covering bounded sets by collections of circles of various radii},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {18--33},
     year = {2020},
     volume = {31},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2020_31_a1/}
}
TY  - JOUR
AU  - A. L. Kazakov
AU  - P. D. Lebedev
AU  - A. A. Lempert
TI  - On covering bounded sets by collections of circles of various radii
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2020
SP  - 18
EP  - 33
VL  - 31
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2020_31_a1/
LA  - en
ID  - IIGUM_2020_31_a1
ER  - 
%0 Journal Article
%A A. L. Kazakov
%A P. D. Lebedev
%A A. A. Lempert
%T On covering bounded sets by collections of circles of various radii
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2020
%P 18-33
%V 31
%U http://geodesic.mathdoc.fr/item/IIGUM_2020_31_a1/
%G en
%F IIGUM_2020_31_a1
A. L. Kazakov; P. D. Lebedev; A. A. Lempert. On covering bounded sets by collections of circles of various radii. The Bulletin of Irkutsk State University. Series Mathematics, Tome 31 (2020), pp. 18-33. http://geodesic.mathdoc.fr/item/IIGUM_2020_31_a1/

[1] Bánhelyi B., Palatinus E., Lévai B. L., “Optimal circle covering problems and their applications”, Cent. Eur. J. Oper. Res., 23:4 (2015), 815–832 | DOI | MR

[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, 77:2 (2016), 332–343 | DOI | MR | Zbl

[3] Dorninger D., “Thinnest covering of the Euclidean plane with incongruent circles”, Anal. Geom. Metr. Spaces, 5:1 (2017), 40–46 | DOI | MR | Zbl

[4] Florian A., Heppes A., “Solid Coverings of the Euclidean Plane with Incongruent Circles”, Discrete Comput. Geom., 23:2 (2000), 225–245 | DOI | MR | Zbl

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

[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, 76:8 (2015), 1463–1470 | DOI | Zbl

[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, 29:1 (2019), 69–79 | DOI | MR

[8] Preparata F. P., Shamos M. I., Computational Geometry: An Introduction, Springer-Verlag Publ, NY, 1985, 396 pp. | MR

[9] Toth L. F., Regular figures, Pergamon Press Book Publ, NY, 1964, 339 pp. | MR | Zbl

[10] Toth L. F., “Solid circle-packings and circle-coverings”, Studia Sci. Math. Hungar., 3 (1968), 401–409 | MR | Zbl

[11] Toth F. G., “Covering the plane with two kinds of circles”, Discrete Comput. Geom., 13:3–4 (1995), 445–457 | DOI | MR | Zbl