П.Д. Лебедев, А.Л. Казаков. Построение оптимальных покрытий плоских фигур кругами различного радиуса ... C. 137-148

УДК 514.174.3

MSC: 52C15, 49K10

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

Теоремы 1 и 2 доказаны П.Д. Лебедевым при поддержке грантов РФФИ, проекты 18-01-00221 и 18-31-00018 мол_а, и при финансовой поддержке постановления № 211 Правительства Российской Федерации, контракт № 02.A03.21.0006. Вычислительный эксперимент выполнен А.Л. Казаковым при поддержке гранта РФФИ, проект 18-07-00604.

Рассматривается задача о построении оптимального покрытия плоской фигуры  $M$ объединением заданного числа кругов. Считается, что радиус  каждого круга в общем случае различается и равен  произведению индивидуального для него положительного коэффициента на общий для всех элементов покрытия параметр $r.$ Критерием оптимальности выбрана минимизация величины $r$ при условии, что множество $M$ вложено в объединение кругов. Для набора точек $S$ выписано значение величины $r,$ определяющей минимальный радиус кругов с центрами в точках из $S,$ реализующих покрытие $M.$ Найдены выражения, позволяющие аналитически описать зоны влияния, так называемые обобщенные зоны Дирихле, точек из $S,$ которые существенно отличаются от выражений для случая конгруэнтных кругов. Предложена процедура итерационной коррекции координат $S $ на базе отыскания чебышевских центров областей влияния точек.  Показано, что она не ухудшает свойства покрытия, при этом ее параметры можно менять в процессе запуска программного комплекса.  Проведены численные эксперименты по построению оптимальных покрытий наборами кругов (при различных коэффициентах, задающих радиус каждого из них). В качестве фигур $M$ взяты различные выпуклые многоугольники, выполнена визуализация результатов.

Ключевые слова: оптимальное покрытие, обобщенная зона Дирихле, чебышевский центр, итерационный алгоритм, минимизация

СПИСОК ЛИТЕРАТУРЫ

1.   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. P. 1463–1470. doi: 10.1134/S0005117915080111 

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. P. 332–343. doi: 10.1134/S0005117916020090 

3.   Preparata F.P., Shamos M.I. Computational geometry: An introduction. N Y: Springer-Verlag, 1985. 398 p. doi: 10.1007/978-1-4612-1098-6 

4.   Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. Москва: Физматлит, 1958. 364 с.

5.   Казаков А.Л., Лебедев П.Д. Алгоритмы построения наилучших $n$-сетей в метрических пространствах// Автоматика и телемеханика. 2017. №7. С. 141–155. doi: 10.1134/S0005117917070104 

6.   Lempert, A., Le, Q.M. Multiple covering of a closed set on a plane with non-Euclidean metrics // IFAC-PapersOnLine. 2018. Vol. 51, no. 32. P. 850–854. doi: 10.1016/j.ifacol.2018.11.439 

7.   Toth L.F. Solid circle-packings and circle-coverings // Studia Sci. Math. Hungar. 1968. Vol. 3. P. 401–409.

8.   Toth F. G., Covering the plane with two kinds of circles // Discrete Comput. Geom. 1995. Vol. 13, no. 3-4. P. 445–457. doi: 10.1007/BF02574055 

9.   Florian A., Heppes A. Solid coverings of the Euclidean plane with incongruent circles// Discrete Comput. Geom. 2000. Vol. 23, no. 2. P. 225–245. doi: 10.1007/PL00009497 

10.   Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles // Anal. Geom. Metr. Spaces. 2017. Vol. 5, no. 1. P. 40–46. doi: 10.1515/agms-2017-0002 

11.   Banhelyi B., Palatinus E, Levai B.L. Optimal circle covering problems and their applications // Central Europ. J. Oper. Research. 2015. Vol. 23, no. 4. P. 815–832. doi: 10.1007/s10100-014-0362-7 

12.   Kazakov A.L., Lempert A.A., Le Q.M. An algorithm for packing circles of two types in a fixed size container with non-Euclidean metric // CEUR-WS. 2017. Vol. 1975. P. 286–297.

13.   Kazakov A., Lempert A., Lebedev P. Congruent circles packing and covering problems for multi-connected domains with non-euclidean metric, and their applications to logistics // CEUR-WS. 2017. Vol. 1839. P. 334–343.

14.   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. P. 69–79. doi: 10.2298/YJOR171112010L 

15.   Лебедев П.Д. Итерационные методы построения аппроксимаций оптимальных покрытий невыпуклых плоских множеств // Челяб. физ.-матем. журн. 2019. Т. 4, вып. 1. С. 5–17. doi: 10.24411/2500-0101-2019-14101 

16.   Брусов В.С., Пиявский С.А. Вычислительный алгоритм оптимального покрытия областей плоскости // Журн. вычисл. математики и мат. физики. 1971. Т. 11, no. 2. С. 304–312.

17.   Гаркави А.Л. О чебышевском центре и выпуклой оболочке множества // Успехи мат. наук. 1964. Т. 19, №6 (120). C. 139–145.

18.   Пшеничный Б. Н. Выпуклый анализ и экстремальные задачи. М., Наука, 1980. 320 с.

19.   Лебедев П.Д. Программа вычисления оптимального покрытия полусферы набором сферических сегментов. Свидетельство о государственной регистрации №2015661543 от 29.10.2015.

Поступила 2.04.2019

После доработки 14.05.2019

Принята к публикации 20.05.2019

Лебедев Павел Дмитриевич
канд. физ.-мат. наук,
старший науч. сотрудник
Институт математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет
г. Екатеринбург
e-mail: pleb@yandex.ru

Казаков Александр Леонидович
д-р физ.-мат. наук
главный науч. сотрудник
Ин-т динамики систем и теории управления им. В.М.Матросова СО РАН
г. Иркутск
e-mail: kazakov@icc.ru

Ссылка на статью: П.Д. Лебедев, А.Л. Казаков. Построение оптимальных покрытий плоских фигур кругами различного радиуса // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 2. С. 137-148.

English

P.D. Lebedev, A.L. Kazakov. Construction of optimal covers by disks of different radii for convex planar sets

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

Received April 2, 2019

Revised May 14, 2019

Accepted May 20, 2019

Funding Agency:Theorems 1 and 2 were proved by Lebedev with support from the Russian Foundation for Basic Research (project nos. 18-01-00221 and 18-31-00018 mol_a) and from the Russian Academic Excellence Project (agreement no. 02.A03.21.0006 of August 27, 2013, between the Ministry of Education and Science of the Russian Federation and Ural Federal University). The computational experiment was carried out by Kazakov with support from the Russian Foundation for Basic Research (project no. 18-07-00604).

Pavel Dmitrievich Lebedev, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia,
e-mail: pleb@yandex.ru

Aleksandr Leonidovich Kazakov, Dr. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory of the Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia,
e-mail: kazakov@icc.ru

Cite this article as: P.D.Lebedev, A.L.Kazakov. Construction of optimal covers by disks of different radii for convex planar sets, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2019, vol. 25, no. 2, pp. 137–148.

[References -> on the "English" button bottom right]