Страница публикации

Численные методы построения упаковок из различных шаров в выпуклые компакты

Тип публикации: Статья в журнале

Тип материала: Текст

Авторы: Лебедев П.Д., Казаков А.Л., Лемперт А.А.

Журнал: Труды Института математики и механики УРО РАН

Язык публикации: russian

Том: 26

Номера страниц: 173-187

Количество страниц: 15

Номер: 2

Год публикации: 2020

Отчетный год: 2020

Переводная версия: {"id":5679,"authors":"Lebedev P. D., Kazakov A.L., Lempert A.A.","authors_count":3,"title":"Numerical methods for the construction of packings of different balls into convex compact sets","journal":"Trudy Instituta Matematiki i Mekhaniki URO RAN","year":2020,"reportYear":2020,"volume":"26","number":"2","month":null,"url":"","pages":"173-187","address":"","type":"\u0422\u0435\u043a\u0441\u0442","publisher":"","edition":"","language":"english","classification":"\u0421\u0442\u0430\u0442\u044c\u0438 \u0432 \u0437\u0430\u0440\u0443\u0431\u0435\u0436\u043d\u044b\u0445 \u0438 \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u043d\u044b\u0445 \u0436\u0443\u0440\u043d\u0430\u043b\u0430\u0445","annotation":"The problem of an optimal packing of incongruent balls into a convex compact set is studied. We consider sets of balls whose radii are proportional to a specified parameter r. The aim is to maximize r. The maximum possible number of different types of balls is three. The problem belongs to the class of NP-hard problems and is solved numerically. We propose algorithms based on partitioning the given compact set into zones of influence of the centers of the elements (generalized Dirichlet zones). The partition is constructed using the optical-geometric approach developed by the authors earlier. A preliminary result is obtained and then improved by a geometric algorithm based on a step-by-step shift of points aimed at maximizing the radius of the current ball. To find the shift direction, we construct the superdifferential of the function equal to the maximum radius of a packed ball centered at the current point. We derive a formula for the maximum growth direction of this function. The developed algorithms are implemented as a software complex for the construction of a ball packing of a compact set. A numerical experiment was carried out for several examples. Packings with balls of different radii are constructed for containers of different shapes: a cube, a sphere, and a cylinder.","published_at":null,"doi":"10.21538\/0134-4889-2020-26-2-173-187","is_to_print":0,"is_special":0,"is_wos":1,"is_scopus":1,"is_risc":0,"is_editable":0,"publication_type_id":1,"added_by_rb_user_id":null,"notes":"","created_at":"2020-07-17 02:14:43","updated_at":"2020-09-29 05:25:55","translated_id":null,"quartile":"Q5","series":"","is_vak":0,"conference":null,"is_public_pdf":0,"eid":null,"wosid":null,"quartile_scopus":null,"report_type":null,"speaker":0,"is_wl":0,"quartile_wl":null,"count_pages":15,"date_event_start":null,"date_event_end":null,"location_event":null,"lvl_event":null,"link_event":null,"title_event":null,"is_affiliation_idstu":null,"is_expert_opinion":null,"quartile_vak":null,"id_author_reference":null,"is_cr":null,"quartile_cr":null,"registration_number":null}

DOI: 10.21538/0134-4889-2020-26-2-173-187

Аннотация: Исследуется проблема оптимальной упаковки неравных шаров в выпуклый компакт. Рассматриваются наборы шаров, радиусы которых пропорциональны заданному параметру r. Максимизация последнего выбрана в качестве критерия оптимальности. Наибольшее возможное количество различных типов шаров равно трем. Задача относится к классу NP-трудных и исследуется численно. Предложены алгоритмы, основанные на сегментации заданного компакта на зоны влияния центров элементов упаковки (обобщенные зоны Дирихле). Разбиение строится с использованием оптико-геометрического подхода, развиваемого в последние годы авторами. После получения промежуточного результата выполняется процедура улучшения с помощью разработанного геометрического алгоритма. В качестве его основы использованы методы, базирующиеся на пошаговом сдвиге точек с целью максимизации радиуса текущего шара. Для отыскания направления сдвига строится супердифференциал функции, равной максимальному радиусу элемента упаковки с центром в текущей точке. Выведена формула, позволяющая определить направление максимального роста данной функции. Разработанные алгоритмы реализованы в виде программного комплекса для построения упаковок шаров в компакт. Выполнен численный эксперимент, в ходе которого рассмотрено несколько примеров. Построены упаковки шаров разного радиуса для тел различной формы: куба, шара, цилиндра.

Индексируется WOS: Нет

Индексируется Scopus: Нет

Индексируется УБС: Нет

Индексируется РИНЦ: Да

Индексируется ВАК: Нет

Индексируется CORE: Нет