RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2019 Volume 25, Number 2, Pages 137–148 (Mi timm1630)

This article is cited in 2 papers

Construction of optimal covers by disks of different radii for convex planar sets

P. D. Lebedevab, A. L. Kazakovc

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg
c Matrosov Institute for System Dynamics and Control Theory of Siberian Branch of Russian Academy of Sciences, Irkutsk

Abstract: We consider the problem of constructing an optimal cover of a planar set $M$ by the union of a given number of disks. In the general case, the radii of the disks are assumed to be different; each radius is the product of some positive factor specific for each disk and a parameter $r$, which is common for all elements of the cover. The optimality criterion is the minimum of $r$ under the condition that $M$ is a subset of the union of the disks. For a set of points $S$, we write the value of $r$ that defines the minimum radius of the disks centered at the points of $S$ and implementing a cover of $M$. Expressions are found that analytically describe the impact zones (the so-called generalized Dirichlet zones) of the points of $S$, which differ significantly from the expressions for the case of congruent circles. A procedure for the iterative correction of coordinates of $S$ based on finding Chebyshev centers of impact zones of points is proposed. It is shown that the procedure does not degrade the properties of the cover, while its parameters can be changed in the process of starting the software complex. Numerical experiments on the construction of optimal covers by families of disks were carried out with different coefficients defining the radii of the disks. Various convex polygons were taken as the set $M$, and the results were visualized.

Keywords: optimal cover, generalized Dirichlet zone, Chebyshev center, iterative algorithm, minimization.

UDC: 514.174.3

MSC: 52C15, 49K10

Received: 02.04.2019

DOI: 10.21538/0134-4889-2019-25-2-137-148



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024