On Covering Bounded Sets by Collections of Circles of Various Radii

Abstract

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.

Keywords

• optimization
• circle covering problem
• generalized dirichlet zone
• chebyshev center
• iterative algorithm
• computational experiment