П.Д. Лебедев, А.Л. Казаков. Итерационные алгоритмы построения наилучших покрытий выпуклых многогранников наборами различных шаров ... С. 116-129

УДК 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]