On Covering Bounded Sets by Collections of Circles of Various Radii
Авторы: Kazakov A.L., Lebedev P.D., Lempert A.A.
Журнал: The Bulletin of Irkutsk State University. Series: Mathematics
Отчётный год: 2020
Аннотация: 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.
Индексируется WOS: 1
Индексируется Scopus: 1
Индексируется РИНЦ: 1
Публикация в печати: 0
Добавил в систему: