рус eng
«ИЗВЕСТИЯ ИРКУТСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА». СЕРИЯ «МАТЕМАТИКА»
«IZVESTIYA IRKUTSKOGO GOSUDARSTVENNOGO UNIVERSITETA». SERIYA «MATEMATIKA»
«THE BULLETIN OF IRKUTSK STATE UNIVERSITY». SERIES «MATHEMATICS»
ISSN 1997-7670 (Print)
ISSN 2541-8785 (Online)

Список выпусков > Серия «Математика». 2023. Том 46

Алгоритмы построения оптимального покрытия плоских фигур наборами кругов линейно различающихся радиусов

Автор(ы)
П. Д. Лебедев1,2, К. Л. Стойчин1

1Уральский федеральный университет им. Б. Н. Ельцина, Екатеринбург, Российская Федерация

2Институт математики и механики им. Н. Н. Красовского УрО РАН, Екатеринбург, Российская Федерация

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

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

Стойчин Красимир Людмилов, аспирант, Уральский федеральный университет, Екатеринбург, 620002, Российская Федерация, k001kk96@mail.ru

Ссылка для цитирования
Лебедев П. Д., Стойчин К. Л. Алгоритмы построения оптимального покрытия плоских фигур наборами кругов линейно различающихся радиусов // Известия Иркутского государственного университета. Серия Математика. 2023. Т. 46. C. 35–50. https://doi.org/10.26516/1997-7670.2023.46.35
Ключевые слова
покрытие кругами, область доминирования, зона Дирихле, чебышевский центр, минимизация
УДК
514.174.3
MSC
41A50, 52C15
DOI
https://doi.org/10.26516/1997-7670.2023.46.35
Литература
  1. Астраков С. Н., Ерзин А. И., Залюбовский В. В. Сенсорные сети и покрытие плоскости кругами// Дискретный анализ и исследование операций. 2009. Т. 16, № 3. C. 3–19. URL: https://www.mathnet.ru/rus/da571
  2. Астраков С. Н., Квашнин А. Г., Короленко Л. А. Построение эффективных сенсорных сетей с учётом стоимостных затрат // Математические структуры и моделирование. 2017. № 3(43). C. 50–62. eLIBRARY ID: 30069584
  3. Брусов В. С., Пиявский С. А. Вычислительный алгоритм оптимального покрытия областей плоскости // Журнал вычислительной математики и математической физики. 1971. Т. 11, № 2. С. 304–312. https://doi.org/10.1016/0041-5553(71)90161-3
  4. Галиев Ш. И., Хорьков А. В. Многократные покрытия кругами равностороннего треугольника, квадрата и круга// Дискретный анализ и исследование операций. 2015. Т. 22, № 6 C. 5–28. https://doi.org/10.17377/daio.2015.22.482
  5. Гаркави А. Л. О чебышевском центре и выпуклой оболочке множества // Успехи математических наук. 1964. Т. 19, вып. 6. С. 139–145.
  6. 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
  7. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы : в 2 т. : пер. с англ. М. : Мир, 1990.
  8. Лебедев П. Д. Итерационные методы построения аппроксимаций оптимальных покрытий невыпуклых плоских множеств// Челябинский физико-математический журнал. 2019. Т. 4, вып. 1. С. 5–17. https://doi.org/10.24411/2500-0101-2019-14101
  9. Лебедев П. Д., Казаков А. Л. Построение оптимальных покрытий выпуклых плоских фигур кругами различного радиуса// Труды Института математики и механики УрО РАН. 2019. Т. 25, № 2. С. 137–148. https://doi.org/10.21538/0134-4889-2019-25-2-137-148
  10. Лебедев П. Д., Кувшинов О. А. Алгоритмы построения субоптимальных покрытий плоских фигур кругами в классах регулярных решеток// Известия Института математики и информатики Удмуртского государственного университета. 2023. Т. 61. С. 76–93. https://doi.org/10.35634/2226-3594-2023-61-05
  11. Миклуш В. А., Татарникова Т. М. Решение задачи расположения датчиков различной физической природы при организации беспроводной сенсорной сети с топологией Mesh// Успехи современной радиоэлектроники. 2022. Т. 76, № 12. С. 15–20. https://doi.org/10.18127/j20700784-202212-03
  12. Петунин А. А., Ченцов А. Г., Ченцов, П. А. К вопросу о маршрутизации перемещений при листовой резке деталей // Вестник ЮУрГУ. Серия Математическое моделирование и программирование. 2017. Т. 10, № 3. С. 25–39. https://doi.org/10.14529/mmp170303
  13. Сосов Е. Н. Метрическое пространство всех 𝑁-сетей геодезического пространства// Ученые записки Казанского государственного университета. Серия физико-мататических наук. 2009. Т. 15, № 4. С. 136–149. https//www.mathnet.ru/rus/uzku771
  14. Тахонов И. В. О некоторых задачах покрытия плоскости кругами// Дискретный анализ и исследование операций. 2014. Т. 21, № 1 (115). С. 84–102. eLIBRARY ID: 21277195. URL: https://www.mathnet.ru/rus/da762
  15. Чен К., Джиблин П., Ирвинг А. MATLAB в математических исследованиях. М. : Мир, 2001.
  16. Kazakov A. L., Lempert A. A. On Mathematical Models for Optimization Problem of Logistics Infrastructure // Intern. J. of Artificial Intelligence. 2015. Vol. 13, N 1. P. 200–210. http://www.ceser.in/ceserp/index.php/ijai/article/view/3537
  17. Kazakov A., Lempert A., Le Q. M. On the thinnest covering of fixed size containers with non-Euclidean metric by incongruent circles // Communications in Computer and Information Science. 2019. Vol. 1090. P. 195–206. https://doi.org/10.1007/978-3-030-33394-2_15
  18. Kazakov A., Lempert A., Le Q. M. On Multiple Coverings of Fixed Size Containers with Non-Euclidean Metric by Circles of Two Types // Communications in Computer and Information Science. 2020. Vol. 1275. P. 120–132. DOI: 10.1007/978-3-030-58657-7_12.
  19. Lempert A., Kazakov A., Le Q. Mung. On reserve and double covering problems for the sets with non-Euclidean metrics // Yugoslav Journal of Operations Research. 2019. Vol. 21, N 1. https://doi.org/10.2298/YJOR171112010L
  20. T´oth F. G. Covering the plane with two kinds of circles// Discrete & Computational Geometry. 1995. Vol. 13, Is. 3–4. P. 445–457. https://doi.org/10.1007/BF02574055

Полная версия (русская)