Алгоритмы построения субоптимальных покрытий плоских фигур кругами в классах регулярных решеток
Ключевые слова:
покрытие, круг, решетка Браве, хаусдорфово отклонение, минимизация
Аннотация
Рассматривается задача о покрытии компактного плоского множества $M$ набором из конгруэнтных кругов. При этом считается, что центры кругов принадлежат некоторой решетке. Критерием оптимальности в одном случае выбирается минимум числа элементов покрытия, а в другом — минимум хаусдорфова отклонения объединения элементов покрытия от множества $M$. Для решения задач к решетке можно применять преобразования параллельного переноса и поворота с центром в начале координат. Доказаны утверждения относительно достаточных условий на наборы кругов, обеспечивающих решение задач. Предложены численные алгоритмы, основанные на минимизации хаусдорфова отклонения между двумя плоскими компактами. Приведено решение ряда примеров для различных фигур $M$.
Литература
1. Красовский Н.Н. Некоторые задачи теории устойчивости движения. М.: Физматгиз, 1959.
2. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Физматлит, 1974.
3. Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. Вып. 6. С. 87-100. https://www.mathnet.ru/rus/at5161
4. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. В 2-х т. М.: Мир, 1990.
5. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 1958.
6. Ушаков В.Н., Лебедев П.Д. Алгоритмы оптимального покрытия множеств на плоскости $\mathbb R^2$ // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2016. T. 26. Вып. 2. C. 258-270. https://doi.org/10.20537/vm160212
7. Лебедев П.Д., Лемперт А.А., Казаков А.Л. Алгоритмы построения оптимального покрытия плоских фигур в динамической метрике // Известия Института математики и информатики Удмуртского государственного университета. 2022. Т. 60. С. 58-72. https://doi.org/10.35634/2226-3594-2022-60-04
8. Ушаков В.Н., Лебедев П.Д., Лавров Н.Г. Алгоритмы построения оптимальных упаковок в эллипсы // Вестник Южно-Уральского государственного университета. Серия «Математическое моделирование и программирование». 2017. T. 10. Вып. 3. C. 67-79. https://doi.org/10.14529/mmp170306
9. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles // Analysis and Geometry in Metric Spaces. 2017. Vol. 5. Issue 1. P. 40-46. https://doi.org/10.1515/agms-2017-0002
10. Prosanov R. On a relation between packing and covering densities of convex bodies // Discrete and Computational Geometry. 2021. Vol. 65. Issue 4. P. 1028-1037. https://doi.org/10.1007/s00454-019-00121-x
11. Bánhelyi B., Palatinus E, Lévai B.L. Optimal circle covering problems and their applications // Central European Journal of Operations Research. 2015. Vol. 23. Issue 4. P. 815-832. https://doi.org/10.1007/s10100-014-0362-7
12. Nasab H.H., Tavana M., Yousefi M. A new heuristic algorithm for the planar minimum covering circle problem // Production and Manufacturing Research. 2014. Vol. 2. Issue 1. P. 142-155. https://doi.org/10.1080/21693277.2014.895917
13. Birgin E.G., Gómez W., Haeser G., Mito L.M., Santos D.O. An augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem // Computational and Applied Mathematics. 2020. Vol. 39. Issue 1. Article number: 10. https://doi.org/10.1007/s40314-019-0991-5
14. Birgin E.G., Laurain A., Massambone R., Santana A.G. A shape optimization approach to the problem of covering a two-dimensional region with minimum-radius identical balls // SIAM Journal on Scientific Computing. 2021. Vol. 43. Issue 3. P. A2047-A2078. https://doi.org/10.1137/20m135950x
15. Zong Chuanming. Packing, covering and tiling in two-dimensional spaces // Expositiones Mathematicae. 2014. Vol. 32. Issue 4. P. 297-364. https://doi.org/10.1016/j.exmath.2013.12.002
16. Клюев Л. Оптимизация C++: совмещаем скорость и высокий уровень. Доклад Яндекса: [Электронный ресурс]. (Дата обращения: 29.01.2023). https://habr.com/ru/company/yandex/blog/522900/
17. Сухарев А.Г., Тимохов А.В., Федоров В.В. Методы оптимизации: учебник и практикум для бакалавриата и магистратуры. М.: Юрайт, 2014.
18. Ушаков В.Н., Лахтин А.С., Лебедев П.Д. Оптимизация хаусдорфова расстояния между множествами в евклидовом пространстве // Труды Института математики и механики УрО РАН. 2014. Т. 20. № 3. C. 291-308. https://www.mathnet.ru/rus/timm1101
19. Danilov D.I., Lakhtin A.S. Optimization of the algorithm for determining the Hausdorff distance for convex polygons // Ural Mathematical Journal. 2018. Vol. 4. No. 1. P. 14-23. https://doi.org/10.15826/umj.2018.1.002
20. Гаркави А.Л. О чебышёвском центре и выпуклой оболочке множества // Успехи математических наук. 1964. Т. 19. Вып. 6 (120). С. 139-145. https://www.mathnet.ru/rus/rm6276
21. Чен К., Джиблин П., Ирвинг А. MATLAB в математических исследованиях. М.: Мир, 2001.
22. Кувшинов О.А. О геометрии овала Кассини, его мере невыпуклости и $\varepsilon$-слое // Известия Института математики и информатики Удмуртского государственного университета. 2022. Т. 60. С. 34-57. https://doi.org/10.35634/2226-3594-2022-60-03
23. Glazyrin A. Covering a ball by smaller balls // Discrete and Computational Geometry. 2019. Vol. 62. Issue 4. P. 781-787. https://doi.org/10.1007/s00454-018-0010-4
2. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Физматлит, 1974.
3. Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. Вып. 6. С. 87-100. https://www.mathnet.ru/rus/at5161
4. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. В 2-х т. М.: Мир, 1990.
5. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 1958.
6. Ушаков В.Н., Лебедев П.Д. Алгоритмы оптимального покрытия множеств на плоскости $\mathbb R^2$ // Вестник Удмуртского университета. Математика. Механика. Компьютерные науки. 2016. T. 26. Вып. 2. C. 258-270. https://doi.org/10.20537/vm160212
7. Лебедев П.Д., Лемперт А.А., Казаков А.Л. Алгоритмы построения оптимального покрытия плоских фигур в динамической метрике // Известия Института математики и информатики Удмуртского государственного университета. 2022. Т. 60. С. 58-72. https://doi.org/10.35634/2226-3594-2022-60-04
8. Ушаков В.Н., Лебедев П.Д., Лавров Н.Г. Алгоритмы построения оптимальных упаковок в эллипсы // Вестник Южно-Уральского государственного университета. Серия «Математическое моделирование и программирование». 2017. T. 10. Вып. 3. C. 67-79. https://doi.org/10.14529/mmp170306
9. Dorninger D. Thinnest covering of the Euclidean plane with incongruent circles // Analysis and Geometry in Metric Spaces. 2017. Vol. 5. Issue 1. P. 40-46. https://doi.org/10.1515/agms-2017-0002
10. Prosanov R. On a relation between packing and covering densities of convex bodies // Discrete and Computational Geometry. 2021. Vol. 65. Issue 4. P. 1028-1037. https://doi.org/10.1007/s00454-019-00121-x
11. Bánhelyi B., Palatinus E, Lévai B.L. Optimal circle covering problems and their applications // Central European Journal of Operations Research. 2015. Vol. 23. Issue 4. P. 815-832. https://doi.org/10.1007/s10100-014-0362-7
12. Nasab H.H., Tavana M., Yousefi M. A new heuristic algorithm for the planar minimum covering circle problem // Production and Manufacturing Research. 2014. Vol. 2. Issue 1. P. 142-155. https://doi.org/10.1080/21693277.2014.895917
13. Birgin E.G., Gómez W., Haeser G., Mito L.M., Santos D.O. An augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem // Computational and Applied Mathematics. 2020. Vol. 39. Issue 1. Article number: 10. https://doi.org/10.1007/s40314-019-0991-5
14. Birgin E.G., Laurain A., Massambone R., Santana A.G. A shape optimization approach to the problem of covering a two-dimensional region with minimum-radius identical balls // SIAM Journal on Scientific Computing. 2021. Vol. 43. Issue 3. P. A2047-A2078. https://doi.org/10.1137/20m135950x
15. Zong Chuanming. Packing, covering and tiling in two-dimensional spaces // Expositiones Mathematicae. 2014. Vol. 32. Issue 4. P. 297-364. https://doi.org/10.1016/j.exmath.2013.12.002
16. Клюев Л. Оптимизация C++: совмещаем скорость и высокий уровень. Доклад Яндекса: [Электронный ресурс]. (Дата обращения: 29.01.2023). https://habr.com/ru/company/yandex/blog/522900/
17. Сухарев А.Г., Тимохов А.В., Федоров В.В. Методы оптимизации: учебник и практикум для бакалавриата и магистратуры. М.: Юрайт, 2014.
18. Ушаков В.Н., Лахтин А.С., Лебедев П.Д. Оптимизация хаусдорфова расстояния между множествами в евклидовом пространстве // Труды Института математики и механики УрО РАН. 2014. Т. 20. № 3. C. 291-308. https://www.mathnet.ru/rus/timm1101
19. Danilov D.I., Lakhtin A.S. Optimization of the algorithm for determining the Hausdorff distance for convex polygons // Ural Mathematical Journal. 2018. Vol. 4. No. 1. P. 14-23. https://doi.org/10.15826/umj.2018.1.002
20. Гаркави А.Л. О чебышёвском центре и выпуклой оболочке множества // Успехи математических наук. 1964. Т. 19. Вып. 6 (120). С. 139-145. https://www.mathnet.ru/rus/rm6276
21. Чен К., Джиблин П., Ирвинг А. MATLAB в математических исследованиях. М.: Мир, 2001.
22. Кувшинов О.А. О геометрии овала Кассини, его мере невыпуклости и $\varepsilon$-слое // Известия Института математики и информатики Удмуртского государственного университета. 2022. Т. 60. С. 34-57. https://doi.org/10.35634/2226-3594-2022-60-03
23. Glazyrin A. Covering a ball by smaller balls // Discrete and Computational Geometry. 2019. Vol. 62. Issue 4. P. 781-787. https://doi.org/10.1007/s00454-018-0010-4
Поступила в редакцию
2023-03-01
Опубликована 2023-05-20
Опубликована 2023-05-20