УДК 514.174.3
MSC: 52C17, 05B40
DOI: 10.21538/0134-4889-2021-27-1-116-129
Полный текст статьи (Full text)
Исследование П.Д. Лебедева поддержано грантом РНФ (проект №19-11-00105).
В теории управления и в различных прикладных областях математики важно выполнять аппроксимацию множеств сложной геометрии наборами унифицированных простых тел. Один из самых распространенных методов — покрытие шарами. В классическом варианте все шары равны, однако интерес представляет и более общая постановка, когда они могут быть различны. В настоящей статье изучается задача о построении покрытия компактного множества M в трехмерном евклидовом пространстве набором из заданного числа шаров, радиусы которых равны произведению общего для всех параметра r на индивидуальный положительный коэффициент. Критерием оптимальности считается минимизация r. Предложены эвристические алгоритмы построения искомых покрытий, основу которых составляют процедуры разбиения M на зоны влияния точек и вычисление их чебышевских центров. Доказаны утверждения о свойствах указанных алгоритмов, выполнена их программная реализация. Проведено численное решение задач о покрытии куба различными наборами шаров двух типов. Намечены возможные направления для проведения дальнейших исследований.
Ключевые слова: оптимизация, покрытие шарами, эвристический алгоритм, чебышевский центр, вычислительный эксперимент
СПИСОК ЛИТЕРАТУРЫ
1. Кеплер И. О шестиугольных снежинках / пер. с латинского Ю. А. Данилова. М.: Наука, 1982. 192 с.
2. Preparata F.P., Shamos M.I. Computational geometry: An Introduction. N Y: Springer-Verlag, 1985. 396 p.
3. Banhelyi B., Palatinus E., Levai B.L. Optimal circle covering problems and their applications // Central European J. Operations Research. 2015. Vol. 23, № 4. P. 815–832. doi: 10.1007/s10100-014-0362-7
4. Широканев А.С., Кирш Д.В., Ильясова Н.Ю., Куприянов А.В. Исследование алгоритмов расстановки коагулятов на изображение глазного дна // Компьютерная оптика. 2018. Т. 42, № 4. С. 712–721. doi: 10.18287/2412-6179-2018-42-4-712-721
5. Hayat H. et al. The State-of-the-art of sensors and environmental monitoring technologies in buildings // Sensors. 2019. Vol. 19, no. 17. art.-no. 3648, 31 p. doi :10.3390/s19173648
6. Бычков И.В., Максимкин Н.Н., Хозяинов И.С., Киселев Л.В. О задаче патрулирования границы акватории, охраняемой группой подводных аппаратов // Технические проблемы освоения Мирового океана. 2013. Т. 5. С. 424–428.
7. Ершов А.А., Ушаков А.В., Ушаков В.Н. Задача о сближении управляемой системы с компактом в фазовом пространстве при наличии фазовых ограничений// Мат. сб., 2019. Т. 210, № 8. C. 29–66. doi 10.4213/sm9141
8. Ушаков В.Н., Ухоботов В.И., Липин А.Е. Об одном дополнении к определению стабильного моста и аппроксимирующей системы множеств в дифференциальных играх// Тр. МИАН. 2019. Т. 304. C. 285–297. doi 10.4213/tm3976
9. Toth L.F. Regular figures. N Y: A Pergamon Press Book The Macmillan Co., 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 & Computational Geometry. 1995. Vol. 13, iss. 3–4. P. 445–457. doi: 10.1007/BF02574055
12. Florian A., Heppes A. Solid Coverings of the Euclidean Plane with Incongruent Circles // Discrete & Computational Geometry. 2000. Vol. 23, iss. 2. P. 225–245. doi: 10.1007/PL00009497
13. 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
14. Banhelyi B., Palatinus E, Levai B.L. Optimal circle covering problems and their applications // Central European J. Operations Research. 2015. Vol. 23, no. 4. P. 815–832. doi: 10.1007/s10100-014-0362-7
15. Takhonov I.I. Multi-level regular coverings of the plane by disks // J. Math. Sci. 2015. Vol. 211, iss. 6. P. 886–901. doi: 10.1007/s10958-015-2642-8
16. Киселева Е.М. Лозовская Л.И., Тимошенко Е.В. Решение непрерывных задач оптимального покрытия шарами с использованием теории оптимального разбиения множеств // Кибернетика и системный анализ. 2009. № 3. C. 98–117.
17. Dumer I. Covering spheres with spheres // Discrete & Computational Geometry. 2006. Vol. 38, iss. 4. P. 665–679. doi: 10.1007/s00454-007-9000-7
18. Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Выч. методы и программирование. 2015. Т. 16. № 2. С. 307–317.
19. Лебедев П.Д., Ушаков А.В. Аппроксимация множеств на плоскости оптимальными наборами кругов // Автоматика и телемеханика. 2012. № 3. P. 79–90.
20. Казаков А.Л., Лебедев П.Д. Алгоритмы построения наилучших n-сетей в метрических пространствах // Автоматика и телемеханика. 2017. № 7. С. 141–155
21. Kazakov A., Lebedev P., Lempert A. On covering bounded sets by collections of circles of various radii // The Bulletin of Irkutsk State University. Ser.: Mathematics. 2020. Vol. 31. P. 18–33. doi: 10.26516/1997-7670.2020.31.18
22. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука. 1980. 320 с.
23. Гаркави А.Л. О чебышевском центре и выпуклой оболочке множества // Успехи мат. наук. 1964. Т. 19, вып. 6. С. 139–145.
24. Шориков А.Ф. Алгоритм решения задачи апостериорного минимаксного оценивания состояний дискретных динамических систем. I // Автоматика и телемеханика. 1996. № 7. С. 130–143.
25. Шориков А.Ф. Алгоритм решения задачи апостериорного минимаксного оценивания состояний дискретных динамических систем. II // Автоматика и телемеханика. 1996. № 9. С. 139–150.
Поступила 11.01.2021
После доработки 20.02.2021
Принята к публикации 25.02.2021
Казаков Александр Леонидович
д-р. физ.-мат. наук, профессор
главный науч. сотрудник
Ин-т динамики систем и теории управления имени В.М. Матросова СО РАН
г. Иркутск,
ведущий науч. сотрудник
Ин-т машиноведения УрО РАН
г. Екатеринбург
e-mail: kazakov@icc.ru
Лебедев Павел Дмитриевич
канд. физ.-мат. наук, старший науч. сотрудник
Ин-т математики и механики им. Н.Н. Красовского УрО РАН
г. Екатеринбург
e-mail: pleb@yandex.ru
Ссылка на статью: П.Д. Лебедев, А.Л. Казаков. Итерационные алгоритмы построения наилучших покрытий выпуклых многогранников наборами различных шаров // Тр. Ин-та математики и механики УрО РАН. 2021. Т. 27, № 1. С. 116-129
English
P.D. Lebedev, A.L. Kazakov. Iterative algorithms for constructing the thinnest coverings of convex polyhedra by sets of different balls
In control theory and various areas of applied mathematics, it is important to approximate sets of complex geometry by unions of simple unified bodies. One of the most common methods here is covering sets with balls. In the classical statement, all the balls are equal; nevertheless, a more general statement is also of interest when the balls can be different. In this paper, we study the problem of constructing a covering of a compact set M in three-dimensional Euclidean space by a set of a given number of balls whose radii are equal to the product of a common parameter r and an individual positive coefficient. The optimality criterion is the minimum of r. We propose heuristic algorithms for constructing such coverings based on splitting the set M into zones of influence of points and finding their Chebyshev centers. Statements about the properties of these algorithms are proved, and the algorithms are implemented. The problems of covering a cube with different sets of balls of two types are solved numerically. Possible directions of further research are outlined and discussed.
Keywords: optimization, ball covering, heuristic algorithm, Chebyshev center, computational experiment
Received January 11, 2021
Revised February 20, 2021
Accepted February 25, 2021
Funding Agency: P.D.Lebedev’s research is supported by the Russian Science Foundation (project no. 19-11-00105).
Alexander Leonidovich Kazakov. Dr. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia; Institute of Engineering Science of the Ural Branch of the Russian Academy of Sciences, Ekaterinburg 620049 Russia, e-mail: kazakov@icc.ru
Pavel Dmitrievich Lebedev, Cand. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: pleb@yandex.ru
Cite this article as: P.D. Lebedev, A.L. Kazakov. Iterative algorithms for constructing the thinnest coverings of polyhedra by sets of different balls, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2021, vol. 27, no. 1, pp. 116–129.
[References -> on the "English" button bottom right]
