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

Казаков Александр Леонидович, д-р физ.-мат. наук, проф. РАН, Институт динамики систем и теории управления имени В.М. Матросова СО РАН, Российская Федерация, 664033, Иркутск, ул. Лермонтова, 134; Иркутский национальный исследовательский технический университет, 664074, Иркутск, ул. Лермонтова, 83 тел.: (3952)453033, e-mail: kazakov@icc.ru

Лебедев Павел Дмитриевич, канд. физ.-мат. наук, Институт математики и механики им. Н.Н. Красовского УрО РАН, Российская Федерация, 620108, Екатеринбург, ул. С. Ковалевской, 16, тел.: (343)3753489, e-mail: pleb@yandex.ru

Лемперт Анна Ананьевна, канд. физ.-мат. наук, Институт динамики систем и теории управления имени В.М.Матросова СО РАН, Российская Федерация, 664033, Иркутск, ул. Лермонтова, 134, тел.: (3952)453030, e-mail: lempert@icc.ru

Kazakov A.L., Lebedev P.D., Lempert A.A. On Covering Bounded Sets by Collections of Circles of Various Radii // Известия Иркутского государственного университета. Серия Математика. 2020. Т. 31. С. 18-33. https://doi.org/10.26516/1997-7670.2020.31.18

1. Banhelyi B., Palatinus E., Levai B.L. Optimal circle covering problems and their applications // Cent. Eur. J. Oper. Res. 2015. Vol. 23, N 4. P. 815–832. https://doi.org/10.1007/s10100-014-0362-7

2. An intelligent management system for the development of a regional transport logistics infrastructure / I. V. Bychkov, A. L. Kazakov, A. A. Lempert, D. S. Bukharov, A. B. Stolbov // Autom. Remote Control. 2016. Vol. 77, N 2. P. 332–343. https://doi.org/10.1134/S0005117916020090

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

4. Florian A., Heppes A. Solid Coverings of the Euclidean Plane with Incongruent Circles // Discrete Comput. Geom. 2000. Vol. 23, N 2. P. 225–245. https://doi.org/10.1007/PL00009497

5. Kazakov A. L., Lebedev P. D. Algorithms for constructing optimal n-networks in metric spaces // Autom. Remote Control. 2017. Vol. 78, N 7. P. 1290–1301. https://doi.org/10.1134/S0005117917070104

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. 2015. Vol. 76, N 8. P. 1463–1470. https://doi.org/10.1134/S0005117915080111

7. Lempert A., Kazakov A. and Le Q. M. On reserve and double covering problems for the sets with non-Euclidean metrics // Yugoslav J. Oper. Research. 2019. Vol. 29, N 1. P. 69–79. https://doi.org/10.2298/YJOR171112010L

8. Preparata F. P., Shamos M. I. Computational Geometry: An Introduction. N. Y. : Springer-Verlag, 1985. 396 p.

9. Toth L. F. Regular figures. N. Y. : A Pergamon Press Book, 1964. 339 p.

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

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