RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. ИММ УрО РАН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. ИММ УрО РАН, 2018, том 24, номер 2, страницы 141–151 (Mi timm1529)  

Итерационные методы построения упаковок из кругов различного диаметра на плоскости

П. Д. Лебедевa, А. Л. Казаковb

a Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
b Институт динамики систем и теории управления имени В.М. Матросова Сибирского отделения Российской академии наук, г. Иркутск

Аннотация: Рассматривается задача о построении оптимальной упаковки из фиксированного числа $n>1$ кругов в общем случае различного радиуса в плоское компактное множество $M$. Считается, что для каждого элемента упаковки задано положительное число такое, что радиус круга равен его произведению на общий для всей упаковки параметр $r$. Критерием оптимальности выбран максимум $r$, что приводит в том числе и к увеличению плотностиупаковки - отношения ее площади к площади фигуры $M$. Основу метода решения задачи составляет итерационное изменение координат центров элементов упаковки $S_n$, дающее возможность увеличивать радиусы кругов. Разработанные вычислительные  процедуры реализуют имитацию отталкивания центра каждого элемента упаковки от близко лежащих других центров и от границы множества $M$. Исследованы дифференциальные свойства функции двух переменных $(x,y)$, значение которой равно максимальному радиусу круга упаковки, располагающегося с центром в точке $(x,y)$. При это координаты центров остальных элементов упаковки считаются фиксированными. При программной реализации используется конструкция чебышевского центра компактного множества. Создан программный комплекс, с его помощью рассмотрен ряд примеров для множеств $M$ различной геометрии. Выполнена визуализация полученных результатов.

Ключевые слова: задача об упаковке кругов, оптимизация, чебышевский центр, супердифференциал, итерационный алгоритм.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-01-00221
18-07-00604
16-06-00464
Работа выполнена при поддержке РФФИ (проекты № 18-01-00221, № 18-07-00604, № 16-06-00464).


DOI: https://doi.org/10.21538/0134-4889-2018-24-2-141-151

Полный текст: PDF файл (276 kB)
Первая страница: PDF файл
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 514.174.2
MSC: 05B40, 28A78, 52C15, 52C26
Поступила в редакцию: 15.03.2018

Образец цитирования: П. Д. Лебедев, А. Л. Казаков, “Итерационные методы построения упаковок из кругов различного диаметра на плоскости”, Тр. ИММ УрО РАН, 24, № 2, 2018, 141–151

Цитирование в формате AMSBIB
\RBibitem{LebKaz18}
\by П.~Д.~Лебедев, А.~Л.~Казаков
\paper Итерационные методы построения упаковок из кругов различного диаметра на плоскости
\serial Тр. ИММ УрО РАН
\yr 2018
\vol 24
\issue 2
\pages 141--151
\mathnet{http://mi.mathnet.ru/timm1529}
\crossref{https://doi.org/10.21538/0134-4889-2018-24-2-141-151}
\elib{http://elibrary.ru/item.asp?id=35060684}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timm1529
  • http://mi.mathnet.ru/rus/timm/v24/i2/p141

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды Института математики и механики УрО РАН
    Просмотров:
    Эта страница:13
    Литература:3
    Первая стр.:3

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018