=Paper=
{{Paper
|id=Vol-1662/opt5
|storemode=property
|title=Алгоритмы построения оптимальных упаковок в трехмерном евклидовом пространстве(Algorithms of optimal packing construction in a 3-dimensional Euclidian space)
|pdfUrl=https://ceur-ws.org/Vol-1662/opt5.pdf
|volume=Vol-1662
|authors=Pavel D. Lebedev,Alexandr A. Uspenskii
}}
==Алгоритмы построения оптимальных упаковок в трехмерном евклидовом пространстве(Algorithms of optimal packing construction in a 3-dimensional Euclidian space)==
https://ceur-ws.org/Vol-1662/opt5.pdf
Алгоритмы построения оптимальных упаковок
в трехмерном евклидовом пространстве
П.Д. Лебедев А.А. Успенский
pleb@yandex.ru uspen@imm.uran.ru
ИММ УрО РАН (Екатеринбург)
Аннотация
Изучается задача о построении оптимальной упаковки равных ша-
ров в компактное множество M в трехмерном евклидовом про-
странстве. Критерием оптимальности считается радиус шаров. Раз-
работаны численные методы, основанные на разбиении M на под-
множества и отыскании шаров, вписанных в них. Доказана тео-
рема о свойствах предложенных алгоритмов. Выполнено конструи-
рование аппроксимаций оптимальных упаковок при большом числе
элементов. Результаты представлены в виде трехмерных иллюстра-
ций.
1 Введение
Аппроксимация множеств объединением унифицированных элементов служит важным фрагментом ре-
шения широкого класса задач теории управления, дифференциальных игр [1], а также прикладных задач
экономики и транспортной логистики [2]. Одним из удобных и в то же время относительно точно передаю-
щих геометрию множества способов его замены является построение упаковки шаров в соответствующем
метрическом пространстве (в котором между любой парой элементов определено расстояние, являющееся
метрикой). Под упаковкой подразумевается объединение шаров B(si , r) равного радиуса r с центрами в
точках si , i = 1, n, вложенных в заданное множество M и пересекающихся только в граничных точках.
Критерием оптимальности естественно считать максимизацию радиуса шаров. Подобные задачи в трех-
мерном пространстве рассматривались в плане численного решения, например, в работах [3, 4].
Естественно, специалисты стремились выявить качественные признаки оптимальных упаковок. В част-
ности, большое значение играет структура упаковки, которая обеспечивает наибольшую плотность при
заполнении всего пространства [5]. Под плотностью упаковки подразумевается отношение суммы объемов
ее шаров к объему множества M . В случае бесконечного множества M плотностью считается предел от-
ношения суммы объема шаров, находящихся внутри шара B(0, ε), к объему M ∩ B(0, ε) при стремлении ε
к бесконечности. При росте числа элементов оптимальной упаковки для компактной фигуры ее геометрия
должна приближаться к той, которая имеет место для всего пространства.
Одним из вариантов оптимальной упаковки пространства является так называемая «гранецентрирован-
ная кубическая решетка», когда центры шаров расположены в узлах некоторой правильной кубической √
решетки и в центрах граней ее кубов (подробнее см. [6, гл. VII]). Плотность данной упаковки равна π/ 18.
Другим вариантом является так называемся гексагональная плотнейшая упаковка, имеющая ту же плот-
ность, но качественно другую структуру [7].
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in
Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org
84
2 Постановка задачи
Ограничимся рассмотрением выпуклых множеств в трехмерном евклидовом пространстве.
Определение 1. Упаковкой Un компактного множества M ⊂ R3 из n шаров радиуса r называется
объединение B(s1 , r) ∪ B(s2 , r) ∪ . . . ∪ B(sn , r) n шаров, для которых выполняются условия
∀i = 1, n B(si , r) ⊆ M,
∀i = 1, n − 1, ∀j = i + 1, n int B(si , r) ∩ int B(sj , r) = ∅.
Здесь int означает внутренность множества.
Сформулируем задачу о нахождении оптимальной упаковки.
Задача 1. Пусть задано ограниченное замкнутое выпуклое множество M ⊂ R3 и число n ∈ N.
Требуется найти упаковку Un∗ множества M , радиус r∗ шаров в которой был бы максимальным.
Ключевым элементом решения задачи 1 является отыскание набора Sn = {si }ni=1 ⊂ M центров шаров
упаковки и вычисление величины
ρ (si , (Sn \ {si }))
RM (Sn ) = min min , ρ (si , ∂M ) , (1)
i=1,n 2
где ρ(a, M ) — расстояние от точки a до замкнутого множества M , ∂M — граница множества M . Выражение
(1) задает максимальный радиус шаров с центрами в точках из Sn , которые образуют упаковку множества
M.
В предельном случае при n = 1 задача 1 сводится к построению шара максимального радиуса, вложен-
ного в M . Заметим, что даже в этом случае ее решение требует сложных вычислений. В некотором смысле
она похожа на задачу об отыскании чебышевского центра и радиуса компакта в R3 [8]. Однако в отличие
от последней задачи, шар максимального радиуса, вложенный в M , может быть не единственным, даже
если M — выпуклый многогранник. Обозначим Υ(M ) = {m∗ ∈ M : ρ(m∗ , ∂M ) = max ρ(m, ∂M )} — множе-
m∈M
ство всех точек множества, в которых достигается максимум расстояния до его границы. По построению,
любая точка из Υ(M ) есть центр шара наилучшей 1-упаковки в M .
Для удобства при построении алгоритмов решения задач 1 формулу (1) можно записать в виде
RM (Sn ) = min ϕi (si ), (2)
i=1,n
где
i 1
ϕ (x) = min min kx − si k, ρ (x, ∂M ) , i = 1, n, (3)
2 j=1,n(j6=i)
здесь k · k означает норму вектора.
Соответственно, процесс отыскания множества Sn центров шаров упаковки можно свести к поэтапной
максимизации функций ϕi (x), i = 1, n, на множестве M . При этом i меняется от 1 до n, точки Sn \ {si }
считаются фиксированными, а si строится как точка локального максимума функции (3) при заданном i.
К форме задачи 1 можно привести различные постановки, известные в геометрии. В частности, И. Нью-
тон сформулировал задачу о так называемом контактном числе шаров — максимальном количестве шаров
единичного радиуса, которые могут одновременно касаться одного такого же шара в R3 (при условии,
что шары пересекаются только в граничных точках). Можно разместить 12 шаров единичного радиуса
с центрами в вершинах правильного икосаэдра так, чтобы они касались одного шара. Но у Ньютона не
было строгого доказательства, что нельзя разместить 13 шаров так, чтобы они имели точку пересечения с
некоторым одним шаром. В терминах данной статьи эту задачу можно сформулировать так. Задано мно-
жество M = {m : 1 6 kmk 6 3}. Требуется решить задачу о построении оптимальной упаковки при n = 13
и вычислить радиус ее шаров r∗ . В работе [9] доказана оценка r∗ < 1, которая означает, что контактное
число равно 12, а не 13. При этом при n = 14 радиус шаров равен r∗ ≈ 0.98, то есть лишь ненамного
меньше 1 [10].
85
3 Методы построения наилучших упаковок
Применительно к ограниченным множествам оптимальные упаковки можно строить аналитически толь-
ко для самых простых случаев. Одним из них является задача 1 при n = 1 для выпуклого многогранника
M . Как уже было отмечено выше, в этом случае требуется отыскать произвольную точку из множества
Υ(M ). Из свойств выпуклых многогранников известно, что шар B(x, r) наибольшего радиуса, вложенный
в M , расположен так, что x ∈ co(∂B(x, r) ∩ ∂M ), где co M означает выпуклую оболочку множества M .
Действительно, если бы данное условие не выполнялось, то можно было бы сдвинуть точку x так, чтобы
расстояние от нее до ближайшей к ней грани многогранника увеличилось, и получить точку x∗ , являю-
щуюся центром шара большего радиуса, вписанного в M . Соответственно, можно искать точку x ∈ M как
точку, равноудаленную от некоторых четырех граней многогранника. В свою очередь, эту задачу мож-
но свести к решению системы линейных уравнений, задающих плоскости, равноудаленные от плоскостей,
содержащих грани M . Если найденная при их решении точка x лежит в M , ее проекции на плоскости
принадлежат соответствующим граням и x не имеет более близких проекций на остальные грани, то она
принадлежит Υ(M ). Данный метод считать некоторым аналогом метода перебора симплексов из вершин
многогранника при отыскании его чебышевского центра [11]. Условие выпуклости является существенным,
поскольку для произвольного невыпуклого многогранника шар наибольшего радиуса, вложенный в него,
может пересекать своей границей ребра или вершины многогранника.
Заметим, что плоскость Λ, равноудаленная от двух плоскостей Λi и Λj , содержащих некоторые две
грани Γi и Γj , является единственной только в том случае, если Λi и Λj параллельны. В противном
случае найдутся две ортогональные бисекторные плоскости Λ∗ и Λ∗ , проходящие через прямую Λi ∩ Λj ,
точки которых лежат на равном расстоянии от Λi и Λj . Однако поскольку по условию M — выпуклый
многогранник, то он полностью лежит в одном из полупространств, ограниченных плоскостью, проходящей
через его грань. Следовательно, всегда можно указать ту единственную плоскость из пары Λ∗ , Λ∗ , непустое
подмножество точек которой вложено в int M . В случае рассмотрения смежных граней обе бисекторные
плоскости имеют непустое пересечение с M , но для одной из них это пересечение совпадает с одной из
граней M , поэтому его точки не могут являться центрами шаров B(r, s) ⊂ M радиуса r > 0.
Решение задачи 1 реализовано на базе методов вычислительной геометрии
Определение 2. Пусть задано компактное множество M и множество Sn , состоящее из n точек. Обла-
стью Дирихле [12, c. 305] точки si ∈ Sn во множестве M называется подмножество
Di (M, Sn ) = {m ∈ M : km − si k = ρ(m, Sn )}.
В случае если Sn ⊂ M , все области Дирихле Di (M, Sn ), i = 1, n, — непустые компакты. Если M —
выпуклое множество, то и области Дирихле в нем выпуклые при произвольном Sn . Если M — выпуклый
многогранник, то множества Di (M, Sn ), i = 1, n, тоже являются по построению выпуклыми многогран-
никами. Для построения областей Дирихле авторы используют так называемую трехмерную диаграмму
Вороного множества Sn , то есть геометрическое место точек, у которых имеются два или более ближай-
ших элемента из Sn (подробнее см. [13]). Диаграмма Вороного в общем случае разбивает пространство на
области, лежащие ближе к одной из точек si , нежели к sj , j = 1, n, j 6= i.
Лемма 1. Пусть задано выпуклое множество M и множества Sn ⊂ M из n попарно различных
точек. Тогда справедливо
∀i = 1, n ϕi (si ) = ρ si , ∂Di (M, Sn ) .
(4)
Доказательство. Без ограничения общности полагаем i = 1. Докажем неравенство
ϕi (s1 ) 6 ρ s1 , ∂D1 (M, Sn ) .
(5)
Допустим, оно не выполняется. Тогда найдется точка m ∈ ∂Di (M, Sn ) такая, что
ks1 − mk < ϕi (s1 ).
По построению области Дирихле, точка m может либо принадлежать ∂M , либо лежать на равном рас-
стоянии от s1 и некоторой другой точки из Sn . Первый случай невозможен, поскольку тогда значение
величины ρ(s1 , ∂M ) не может быть больше, чем ks1 − mk, а значит, и значении функции ϕi (s1 ) тоже. Если
86
реализовался второй случай, то можно указать точку из Sn (без ограничения общности полагаем, что s2 )
такую, что
ks1 − mk = ks2 − mk.
Тогда в силу неравенства треугольника имеет место
ks1 − s2 k 6 ks1 − mk + ks2 − mk = 2ks1 − mk,
следовательно, ϕi (s1 ) 6 ks1 − s2 k/2 6 ks1 − mk. Получилось противоречие.
Докажем неравенство
ϕi (s1 ) > ρ s1 , ∂D1 (M, Sn ) .
(6)
∗
Допустим, оно не выполняется. Тогда найдется точка m , либо принадлежащая ∂M , либо являющаяся
серединой отрезка, с концами соответственно в s1 и в некоторой другой точке из Sn такая, что
ks1 − m∗ k < ρ s1 , ∂D1 (M, Sn ) .
Первый вариант невозможен, поскольку, если точка m∗ лежит на границе множества M и не принадлежит
∂D1 (M, Sn ), то она лежит в некоторой другой области Дирихле Dj (M, Sn ), j > 1. Следовательно, можно
построить отрезок [s1 , m∗ ], у которого конец m∗ лежит вне D1 (M, Sn ). Тогда найдется точка m ∈ [s1 , m∗ ] ∩
∂D1 (M, Sn ). В итоге имеет место неравенство
ks1 − m∗ k > ks1 − mk > ρ s1 , ∂D1 (M, Sn ) .
Получилось противоречие.
Если реализовался второй случай, то можно указать точку из Sn (без ограничения общности полагаем,
что s2 ) такую, что m∗ = (s1 + s2 )/2 и
ks1 − s2 k 6 2ρ s1 , ∂D1 (M, Sn ) .
Если m∗ не принадлежит ∂D1 (M, Sn ) , то она, как и в предыдущем случае, лежит в некоторой области
Дирихле Dj (M, Sn ), j > 1, такой, что ks1 − m∗ k > ksj − m∗ k. Соответственно, отрезок [s1 , m∗ ] минимум в
одной точке m пересекает множество ∂D1 (M, Sn ). Получается противоречие, как и в предыдущем случае.
Из оценок (5) и (6) следуют равенства (4).
На базе леммы 1 разработан алгоритм итерационного улучшения множества точек Sn ⊂ M с позиции
максимизации значения величины (2), представляющий из себя переработку алгоритма из работы [14] для
случая трехмерного пространства.
Алгоритм 1.
1. Переменная i циклически меняется от 1 до n.
2. Строится область Дирихле Di (M, Sn ) с помощью разбиения многогранника M на части диаграммой
Вороного.
3. Посредством перебора всех четверок из числа граней многогранника Di (M, Sn ) находится точка
si ∈ Υ(Di (M, Sn )) — центр шара максимального радиуса, вложенного в Di (M, Sn ). В случае если
b
Υ(Di (M, Sn )) содержит более, чем 1 элемент, то b
si выбирается из них с помощью генератора случай-
ных чисел.
4. В качестве нового значения элемента множества Sn с номером i записывается si := b
si .
5. Заканчивается цикл по i.
Ключевым моментом является то, что Sn меняется на каждом из n циклов, поэтому область Дирихле
Di (M, Sn ) вычисляется не для начального, а для текущего значения n-сети.
Заметим, что алгоритм 1 может быть распространен на евклидово пространство произвольной размерно-
сти m. При этом области Дирихле Di (M, Sn ), i = 1, n, будут выпуклыми многогранниками в пространстве
Rm , а для отыскания максимального вписанного в Di (M, Sn ) шара потребуется перебирать все множества
из m + 1 граней области. Диаграмма Вороного будет состоять из многообразий размерности от m − 1 до 0.
87
Теорема 1. Для произвольного выпуклого многогранника M ⊂ M и произвольного множества из n то-
si }ni=1 удовлетворяет
чек Sn ⊂ M полученное в результате применения к Sn алгоритма 1 множество Sbn = {b
неравенству
RM (Sbn ) > RM (Sn ). (7)
Доказательство. Изменения в множестве Sn происходят только за счет замены точки si на точку из
множества Υ(Di (M, Sn )) в пункте 4. Покажем, что при этом не уменьшается значение (2). Приведем обос-
нование, что для любого множества S n = {si }ni=1 , полученного из Sn путем замены одной из его точек si
на точку b
si , выполнено неравенство
RM (S n ) > RM (Sn ). (8)
Введем по аналогии с (3) функции
i 1
ϕ (x) = min min kx − si k, ρ (x, ∂M ) , i = 1, n.
2 j=1,n(j6=i)
Обозначим через J множество номеров тех точек из S n , для которых выполняется равенство
ksi − sj k
ϕj (sj ) = .
2
Заметим, что неравенство ϕj (sj ) > ϕj (sj ) может иметь место только при j ∈ J.
Действительно, значение функции ϕi (si ) не может быть меньше, чем ϕi (si ) в силу леммы 1. Значит
ϕi (si ) > ϕi (si ). (9)
Если же j 6= i и j ∈ / J, то для точки sj найдется либо точка на границе, лежащая к ней ближе, чем
ksi − sj k/2, либо точка sk ∈ S n (k 6= i, k 6= j) такая, что ksk − sj k < ksi − sj k. Значит, можно записать оценку
/ J) ϕj (si ) > ϕj (si ).
∀j = 1, n (j 6= i, j ∈ (10)
Из определения функций ϕj следует оценка
∀j = 1, n (j 6= i) ϕi (si ) 6 ksi − sj k/2.
По построению множества J имеем
∀j ∈ J ϕj (sj ) > ϕi (si ).
С учетом неравенства (9) запишем
∀j ∈ J ϕj (sj ) > ϕi (si ). (11)
Из (9), (10) и (11) вытекает оценка
∀j ∈ 1, n ϕj (sj ) > ϕj (sj ),
что и дает соотношение (8). Поскольку при доказательстве номер i может быть любым, а переход от
множества Sn к S n может осуществляться любое конечное число раз, то значит верна и оценка (7).
Теорема 1 позволяет сделать вывод о приемлемости использования алгоритма 1 при создании про-
граммного комплекса. Естественно, его применение должно быть многократным в рамках цикла, выход из
которого реализуется в том случае, когда разность между значениям величин RM (Sn ) и RM (Sbn ) меньше
заданного параметра точности δr. Другим параметром, значение которого должно учитываться при при-
нятии решении о завершении работы комплекса, является h(Sbn , Sn ). Если хаусдорфово отклонение новой
n-сети от старой больше δh, то есть возможность улучшать упаковку.
Важной компонентой программного комплекса является процедура генерации первого приближения
множества Sn0 . Она реализована с использованием стохастических методов, позволяющих получать ка-
чественно различные начальные условия для алгоритма 1. В рамках реализованной процедуры каждая
точка si , i = 1, n, генерируется как массив векторов, равных сумме двух элементов. Одно из слагаемых
берется как точка из правильной гранецентрированной кубической решетки (длина ребра l которой зада-
ется в комплексе в качестве
√ параметра, ориентировочно пропорционального диаметру тела M и обратно
пропорционального к 3 n). Другой слагаемое берется как случайный вектор, координаты которого имеют
88
равномерное распределение на отрезка [−ε, ε], причем ε существенно меньше l. Для найденной точки si
выполняется проверка условия, принадлежит ли она M , и не совпадает ли с каким-либо уже записанным
элементом Sn . При стохастической генерации массива точек возможна такая их конфигурация, которая
далека от оптимальной, однако локально устойчива относительно применения алгоритма 1. Например,
если M — куб, а точки si ∈ Sn0 расположены на отрезке, соединяющем центры противоположных граней.
Однако на практике программа запускается многократно при различных значениях Sn0 , что позволяет
отбрасывать подобные упаковки с малым радиусом шаров RM (Sn ).
4 Примеры
Авторами разработан в пакете MATLAB программный комплекс, реализующий построение аппроксима-
ций оптимальных упаковок для выпуклых многогранников. В нем использованы процедуры вычислитель-
ной геометрии, которые раньше применялись для решения прикладных задач, в частности, построения
функции евклидового расстояния до множества, сингулярных линий в задачах быстродействия [15] и оп-
тимальных покрытий [11].
Пример 1. Требуется построить наилучшие упаковки Un для куба M = {(x, y, z) ∈ R3 : |x| 6 1,
|y| 6 1,|z| 6 1} при числе шаров n, равном 20 и 30.
У куба 6 граней Γi , i = 1, 6, являющиеся квадратами. При генерации первоначального приближения
множества Sn применялись стохастические процедуры с ограничением на координаты точек si , i = 1, n,
чтобы они не превышали по модулю 0.9.
При n = 20 радиус шаров аппроксимации оптимальной упаковки в куб M равен r ≈ 0.3412. Ребра куба
M и упаковка шаров U20 представлены на рис. 1 и 2. Массив центров шаров
S20 ≈ {(−0.5312, −0.6547, −0.6300), (−0.6554, −0.5032, 0.0334), (−0.4099, −0.6584, 0.6584),
(−0.6551, 0.0239, −0.6551), (−0.2232, 0.0387, −0.0078), (−0.6587, −0.0223, 0.6587),
(−0.3128, 0.6558, −0.6558), (−0.6566, 0.5764, −0.0656), (−0.6588, 0.6588, 0.6141),
(0.1595, −0.6557, −0.6557), (0.0163, −0.6556, 0.0179), (0.2751, −0.6566, 0.6566),
(0.0336, 0.0602, −0.6553), (0.4485, 0.2764, −0.0266), (0.0378, −0.0009, 0.6514),
(0.6312, 0.6312, −0.6312), (0.0114, 0.6465, 0.3916), (0.6392, 0.4346, 0.6392),
(0.6554, −0.2000, −0.5110), (0.6546, −0.3721, 0.1572)}.
При n = 30 радиус шаров аппроксимации оптимальной упаковки равен r ≈ 0.2953. Ребра куба M и
упаковка шаров U30 представлены на рис. 3 и 4. Массив центров шаров
S30 ≈ {(−0.6895, −0.6895, −0.5598), (−0.6992, −0.6992, 0.2497), (−0.3158, −0.5792, 0.6984),
(−0.1844, −0.3548, −0.6991), (−0.5385, −0.2035, −0.2376), (−0.2228, −0.1535, 0.2774),
(−0.6981, −0.1127, 0.6782), (−0.6964, 0.1627, −0.6964), (−0.2388, 0.3202, −0.2540),
(−0.7000, 0.2081, 0.1682), (−0.1300, 0.2759, 0.6966), (−0.4145, 0.7050, −0.6991),
(−0.7009, 0.7009, −0.1726), (−0.3071, 0.6978, 0.2850), (−0.6977, 0.4912, 0.6977),
(0.3124, −0.6974, −0.6974), (0.5108, −0.6970, −0.1253), (0.1874, −0.6977, 0.3864),
(0.6975, −0.6041, 0.6975), (0.6788, −0.1771, −0.6210), (0.6970, −0.1391, 0.0203),
(0.1361, −0.1900, −0.2119), (0.3189, −0.1316, 0.6970), (0.1327, 0.1569, −0.6995),
(0.6977, 0.3852, −0.2822), (0.2591, 0.6967, 0.4976), (0.6968, 0.2786, 0.4596),
(0.3941, 0.6988, −0.6988), (0.2104, 0.6974, −0.1064), (−0.2123, −0.6912, −0.1008)}.
Пример 2. Требуется построить наилучшие упаковки Un для октаэдра M = {(x, y, z) ∈ R3 : |x| + |y|+
+|z| 6 1} при числе шаров n, равном 20 и 30.
У октаэдра 8 граней Γi , i = 1, 8, являющихся правильными треугольниками. Октаэдр дуален кубу, то
есть вершины одного из этих многогранников — центры граней другого. При генерации первоначального
приближения множества Sn применялись стохастические процедуры с ограничением на координаты точек
si , i = 1, n, чтобы суммы модулей абсциссы, ординаты и аппликаты не превышали 0.9.
89
Рис. 1: Аппроксимация U20 наилучшей упаковки ку- Рис. 2: Аппроксимация U20 наилучшей упаковки ку-
ба M 20-ю шарами: вид 1. ба M 20-ю шарами: вид 2.
Рис. 3: Аппроксимация U30 наилучшей упаковки ку- Рис. 4: Аппроксимация U наилучшей упаковки ку-
30
ба M 30-ю шарами: вид 1. ба M 30-ю шарами: вид 2.
При n = 20 радиус шаров аппроксимации оптимальной упаковки в октаэдр M равен r ≈ 0.1820. Ребра
куба M и упаковка шаров U20 представлены на рис. 5 и 6. Массив центров шаров
S20 ≈ {(0.1345, 0.1368, 0.4123), (0.3002, 0.2731, 0.1137), (−0.1593, −0.2739, −0.1832),
(0.1255, 0.3604, −0.1961), (0.1174, −0.0064, −0.2020), (0.4840, −0.0000, −0.1984),
(0.1073, −0.1141, 0.1479), (0.4692, −0.0477, 0.1652), (−0.2116, 0.4110, −0.0587),
(−0.0055, 0.4289, 0.2462), (−0.1460, −0.3799, 0.1678), (−0.4735, −0.1985, 0.0215),
(0.0000, −0.1794, −0.5031), (0.2918, −0.3925, 0.0001), (0.0001, −0.5910, −0.0924),
(−0.2966, 0.0012, 0.3866), (−0.0000, 0.1874, −0.4947), (−0.1991, 0.0549, 0.0351),
(0.0000, −0.1946, 0.4884), (−0.3838, 0.0074, −0.2852)}.
При n = 30 радиус шаров аппроксимации оптимальной упаковки равен r ≈ 0.1570. Ребра куба M и
упаковка шаров U30 представлены на рис. 7 и 8. Массив центров шаров
S30 ≈ {(0.3017, −0.2316, 0.0835), (−0.0016, −0.4604, −0.2541), (−0.4139, 0.0847, 0.0749),
(−0.2063, −0.2050, −0.3026), (0.1271, −0.2434, 0.3596), (−0.0326, 0.3509, −0.3350),
90
(−0.7188, −0.0000, 0.0000), (−0.1771, 0.0842, −0.4558), (0.4012, −0.0067, 0.3120),
(−0.3074, 0.2362, −0.1956), (−0.3363, −0.3554, −0.0326), (−0.2296, 0.4976, 0.0129),
(−0.0971, −0.1007, −0.0055), (0.5502, 0.1782, 0.0003), (0.0718, 0.0609, 0.2568),
(−0.3080, −0.1648, 0.2488), (−0.1042, −0.4095, 0.2089), (−0.2363, 0.1368, 0.3436),
(−0.0369, 0.2307, 0.0036), (0.5927, −0.1337, 0.0000), (0.2537, 0.0729, −0.0041),
(0.1490, −0.1599, −0.2269), (0.0000, −0.0000, −0.7171), (0.0000, 0.3663, 0.3502),
(−0.0853, −0.6525, −0.0003), (0.4408, 0.0008, −0.2681), (0.1666, 0.1004, −0.4406),
(0.2026, −0.5228, 0.0000), (0.0894, 0.5580, 0.0924), (0.2259, 0.3656, −0.1337)}.
Рис. 5: Аппроксимация U20 наилучшей упаковки ок- Рис. 6: Аппроксимация U наилучшей упаковки ок-
20
таэдра M 20-ю шарами: вид 1. таэдра M 20-ю шарами: вид 2.
Рис. 7: Аппроксимация U30 наилучшей упаковки ок- Рис. 8: Аппроксимация U наилучшей упаковки ок-
30
таэдра M 30-ю шарами: вид 1. таэдра M 30-ю шарами: вид 2.
В процессе построения упаковок в каждом примере параметры окончания работы программного ком-
плекса были равны δr = 10−4 , δh = 10−3 . Для каждого из значений n было выполнено от 10 до 15 запусков
с различными начальными значениями Sn0 . Общее число циклов алгоритма 1 варьировалось от 39 до 77. Во
всех случаях n-сеть пришла к установившемуся значению. При графическом представлении результатов
упаковки показаны под разным углом: в одном случае фронтальная плоскость близка к плоскости xOz, в
другом — к yOz.
91
5 Заключение
Авторами разработан программный комплекс построения оптимальных упаковок шаров в многогран-
ники. Он основан на геометрических алгоритмах максимизации функции (1), которые итерационно изме-
няют заданное множество точек Sn . Для построения начального приближения массива центров шаров Sn
использованы стохастические процедуры, учитывающие геометрию многогранника. Показано, что алго-
ритмы являются монотонными, то есть не уменьшают радиус шаров. Проведено численное моделирование
примеров; построены аппроксимации наилучших упаковок шаров в куб и в правильный октаэдр. Выпол-
нена визуализация результатов.
6 Благодарности
Работа была выполнена при финансовой поддержке РФФИ (проект №16-31-00356-мол_а) и Программы
фундаментальных исследований УрО РАН, проект №15-16-1-13.
Список литературы
[1] Krasovskii N. N., Subbotin A. I. Positional Differential Games. Nauka, Moscow. 1974 (in Russian). =
Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. М.: Наука, 1974.
[2] Kazakov A. L., Lempert A. A. An Approach to Optimization in Transport Logistics. Autom. Remote Control.
72 (7): 1396–1404, 2011.
[3] Yamada S., Kanno J., and Miyauchi M. Multi-sized sphere packing in containers: optimization formula for
obtaining the highest density with two different sized spheres. IPSJ Online Transactions. 4: 126–133, 2011.
[4] Stoyan Y., Yaskov G. Packing congruent spheres into a multi-connected polyhedral domain Intl. Trans. in
Op. Res. 20: 79–99, 2013. DOI: 10.1111/j.1475–3995.2012.00859.x
[5] Conway J. H., Sloane N. J. A. Sphere Packing, Lattices and Groups Springer, New York, 1988.
[6] Töth L. F. Lagerungen in der Ebene, auf der Kugel und im Raum Springer. Springer, Berlin, 1957.
[7] Sloane N. J. A. Scientific American. 250 (1): 116–125, January 1984. DOI: 10.1038/scientificamerican0184-
116
[8] Garkavi A. L. On the Chebyshev center and convex hull of a set. Uspekhi Mat. Nauk. 19 (6), 139–145, 1964.
[9] Schütte K., van der Waerden B. L. Das Problem der dreizehn Kugeln Math. Ann. 125 (1): 325–334, 1953.
DOI:10.1007/BF01343127.
[10] Musin O. R., Tarasov A. S. The Tammes problem for N = 14. E-print, 2014, arXiv: 1410.2536 [math.MG]
[11] Lebedev P. D. and Ushakov V. N. Algorithms for the construction of an optimal cover for sets in three-
dimensional Euclidean space. Tr. IMM UrO RAN. 21 (2): 276–288. 2015.
[12] Brusov V. S., Piyavskii S. L. A computational algorithm for optimally covering a plane region. USSR Comp.
Math. Math. Phys. 11 (2): 17–27, 1971.
[13] Mestetsky L. M. Continuous Morphology of Binary Images: Shapes, Frames, Circulars. Fizmatlit, Moscow,
2009 (in Russian). = Местецкий Л. М. Непрерывная морфология бинарных изображений: фигуры, ске-
леты, циркуляры. М.: Физматлит, 2009.
[14] Kazakov A. L. and Lebedev P. D. Algorithms of Optimal Packing Construction for Planar Compact Sets.
Numerical Methods and Programming. (Vychislitel’nye Metody i Programmirovanie). 16 (3): 307–317, 2015
(in Russian). = Казаков А. Л., Лебедев П. Д. Алгоритмы построения оптимальных упаковок для ком-
пактных множеств на плоскости. Вычислительные методы и программирование. 16 (3): 307–317, 2015.
[15] Lebedev P. D., Uspenskii A. A. On the set of limit values of local diffeomorphisms in wavefront evolution.
Proceedings of the Steklov Institute of Mathematics. 272 (1): 255–270, 2011.
92
Algorithms of optimal packing construction in a 3-dimensional
Euclidian space
Pavel D. Lebedev, Alexandr A. Uspenskii
Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia)
Keywords: optimal packing, polyhedron, Dirichlet domain, distance function, stochastic algorithm.
The problem of optimal equal balls packing construction into the compact set M in a 3-dimensional Euclidian
space is studied. Criteria of optimality is considered radii of the balls. Numerical methods based on splitting
M into subsets and calculating balls inscribed into them are designed. The theorem about suggested algorithm
properties is proved. Constructing optimal packing approximations is produced with large quantity of its elements.
The results are presented as 3-dimensional illustrations.
93