Рассматривается задача об упаковке ¾кругов¿ в выпуклые компактные множества на плоскости. Расстояние между точками считается равным времени, за которое волна в неоднородной среде проходит от одной точки до другой. Считается, что на компактном множестве задана метрика специального вида, называемая вариационной. Критерием оптимальности упаковки выбран радиус ¾кругов¿ при фиксированном их числе. Используются вычислительные методы конструирования границ ¾кругов¿ как волновых фронтов на базе принципов геометрической оптики. Для максимизации их радиуса применяются итерационные алгоритмы, имитирующие отталкивание центров кругов от границ соседних с ними элементов упаковки и от границы выпуклого множества. В них применяются конструкции чебышевского центра, позволяющие сформировать вектор сдвига в нужном направлении. Разработан программный комплекс. Проведено численное моделирования ряда примеров для множеств различной геометрии и при различном распределении скоростей распространения волны на плоскости. Выполнена визуализация результатов.
пространствах постоянной кривизны (гиперболическом и эллиптическом) так, чтобы их плотность была наибольшей. Кроме этого, данная проблема исследовалась в цикле работ Дж. Жирмая (J. Szirmai): в [10] описан способ построения оптимальной упаковки шаров для черепицы Коксeтера (Coxeter tiling) в гиперболическом трехмерном пространстве, в [11] предложен метод, основанный на проективной интерпретации гиперболической геометрии, в [12] расширена задача нахождения наиболее плотной геодезической упаковки шаров для 3-мерных геометрий Тeрстона (Thurston geometries). Авторами ранее в основном исследовалась задача о покрытии [13], задача об упаковке рассматривалась применительно к правильным многоугольникам и кругам на плоскости [14] и правильным многогранникам в трехмерном пространстве [15].
В данной статье мы изучаем круги в метрическом пространстве, в котором расстояние между точками определяется временем распространения сигнала в неоднородной среде. Это обусловлено широким классом практических задач, в которых приходится иметь дело с расположением объектов в условиях различных факторов, изменяющих радиус их зон действия. В случае логистических центров это может быть ландшафт местности, наличие водных преград или лесных массивов [16]. В случае узлов связи их роль могут играть особенности распространения излучения в различных слоях атмосферы [17]. 2
Постановка задачи Рассмотрим компактное множество D щим образом: Здесь f (x; y) непрерывная функция, определенная на множестве D, на которую наложено условие
R2, расстояние между точками a и b которого задано следуюf (a; b) = min 2 (a;b)
Z
d f (x; y)
:
8(x; y) 2 D f (x; y) > 0;
(
Определение 1. Упаковкой Un компактного множества M X из n шаров радиуса r называется объединение Of (x1; r) [ Of (x2; r) [ : : : [ Of (xn; r) из n шаров, для которых выполняются условия 8i = 1; n Of (xi; r)
M; 8i 6= j int Of (xi; r) \ int Of (xj; r) = ?: Здесь int означает объединение внутренних точек множества. Таким образом, набор шаров равного радиуса является упаковкой множества M в том случае, если все они вложены в M и никакие два шара не имеют общих внутренних точек. Поскольку в данной работе рассматриваются метрические пространства размерности два (то есть плоскости), будем далее именовать шары ¾кругами¿.
Обозначим множество всех упаковок множества M , состоящих из n кругов, через n(M ). Ограничимся далее рассмотрением выпуклых множеств [18] ненулевой площади.
Задача 1. Пусть задано ограниченное замкнутое выпуклое множество M и число n 2 N. Требуется найти упаковку Un 2 n(M ), радиус r кругов которой был бы максимальным.
Метрика (
Принципы решения задачи
RM (Sbn) > RM (Sn): RM (Sbn) = im=1in;n 'b(i)(bsi): '(i)(x) = min 1
min
2 j=1;n(j6=i)
Соответственно, процесс отыскания множества Sn центров шаров упаковки можно свести к поэтапной
максимизации функций '(i)(x), i = 1; n; на множестве M . При этом i меняется от 1 до n, точки Sn n fsig
считаются фиксированными, а si строится как точка локального максимума функции (
Можно показать, что максимизацию радиуса кругов упаковки можно свести к циклической коррекции координат отдельных точек. При изменении одной точки si из всей n-сети Sn достаточно требовать, чтобы увеличивалась величина '(i)(si).
Предложение 1. Пусть заданы компакт M , две n-сети Sn = fsigin=1 M и Sbn = fbsigin=1 M и натуральное число i 6 n такие, что 8i = 1; n (i 6= i ) si = si; si 6= bsi : b Если выполняется неравенство min 1
min 2 i=1;n(i6=i ) 1
min
2 i=1;n(i6=i )
f (bsi ; si); hf (bsi ; @M ) ;
(
Методы максимизации радиуса
Авторы развивают методы поэтапной коррекции координат точек n-сети Sn с целью увеличения
значения радиуса (
Определение 2. Чебышевским центром [21] компактного множества M R2 называется такая точка
c(M ), что
sup kc(M )
m2M
mk = inf sup kx
x2R2 m2M
mk:
(
Устанавливаются параметры rz (радиус слоя точек, которые участвуют в формировании сдвига), kz (коэффициент величины сдвига).
Строится множество точек P (i) = fpj: j = 1; n (j 6= i)g пересечения ¾кругов¿ минимального радиуса с центром в точке si c ¾кругами¿ того же радиуса с центрами в точках из Sn n fsig.
На границе выделяется ближайшая в вариационной метрике к si точка p0 (в случае если таких точек несколько, берется произвольная из них) и вычисляется величина f (si; p0).
Строятся кривые j 2 (si; pj), j = 0; n (j 6= i), на которых достигается минимум (
Строятся предельные значения vj касательного вектора на каждой из кривой j, j = 0; n (j 6= i) в точке g при g ! si (параметризация кривой считается заданной от точки pj в сторону si).
Строится предельное значение v0 касательного вектора на каждой из кривой 0 в точке g при g ! si (параметризация кривой считается заданной от точки pj в сторону si).
Строится массив W = fwj: j = 0; n(j 6= i)g векторов, сонаправленных vj, wj =
Rjvj kvjk
; j = 0; n (j 6= i); длина которых зависит от расстояния в вариационной метрике между точками по закону Rj = '(i)(si) + rz f (si; pj); если f (si; pj) < '(i)(si) + rz; j = 0; n (j 6= i): 0; если f (si; pj) > '(i)(si) + rz; Строится чебышевский центр c(W ) массива векторов W , то есть центр круга наименьшего радиуса, в который вложено W .
В качестве новой точки bsi берется
bsi = si + kzc(W ): Данный алгоритм применяется ко всем точкам сети, после чего выполняется оценка, насколько сильно они сдвинулись. Затем цикл построения ¾кругов¿ и их сдвига выполняется программным комплексом многократно. Похожие схемы, например ¾метод возможных направлений¿ и ¾метод проекции градиента¿ описаны, например, в [24, гл. 4].
Результаты моделирования Авторами создан программный комплекс в пакете MATLAB, реализующий представленные выше алгоритмы. Он позволяет вычислять аппроксимации наилучших упаковок для плоских множеств и проводить их визуализацию.
Пример 1. Требуется решить задачу 1 при n = 8 и n = 9 для множества представляющего из себя круг, и функции среды
M = (x; y) 2 R2: (x 6)2 + (y Упаковка показана на рис. 3 При n = 9 радиус r 1:2408. Массив координат центров кругов упаковки
S9
f(3:9712; 5:7055); (6:6622; 5:9282); (4:1623; 7:5196); (7:3137; 7:9031); (2:6583; 6:0678); (9:3284; 6:0565); (5:3684; 5:9526); (8:0186; 5:89); (5:9358; 3:7339)g: Упаковка U9 показана на рис. 4. Рис. 3: Аппроксимация U8 наилучшей упаковки кру- Рис. 4: Аппроксимация U9 наилучшей упаковки круга M 8-ю ¾кругами¿ в примере 2. га M 9-ю ¾кругами¿ в примере 2.
Особенностью среды в данном примере является то, что функция скорости распространения волны f зависит только от одной переменной, а значит среда является слоистой.
Пример 3. Требуется решить задачу 1 при n = 8 и n = 9 для множества M , заданного формулой (
Особенностью среды в данном примере является то, что функция скорости распространения волны f зависит только от расстояния до точки (4:5; 6), а значит среда является радиальной.
Пример 4. Требуется решить задачу 1 при n = 8 и n = 9 для множества представляющего из себя квадрат, и функции среды
M = (x; y) 2 R2: 1 6 x 6 8; 2 6 y 6 9 ; Рис. 5: Аппроксимация U8 наилучшей упаковки кру- Рис. 6: Аппроксимация U9 наилучшей упаковки круга M 8-ю ¾кругами¿ в примере 3. га M 9-ю ¾кругами¿ в примере 3. Рис. 7: Аппроксимация U8 наилучшей упаковки Рис. 8: Аппроксимация U9 наилучшей упаковки квадрата M 8-ю ¾кругами¿ в примере 4. квадрата M 9-ю ¾кругами¿ в примере 4.
В процессе построения упаковок в каждом примере параметры окончания работы программного комплекса были равны dr = 0:02 0:1; Np = 50 200, rz = 0:05 0:1; kz = 0:5. Для каждого из значений n было выполнено от 20 до 30 запусков с различными начальными значениями координат центров Sn(0). Общее число циклов программного комплекса варьировалось от 120 до 270. В работе предложены алгоритмы решения известной задачи об упаковке кругов равного радиуса в компактное множество в пространстве с неевклидовой метрикой специального вида. Их основой служат геометрические конструкции построения волновых фронтов, ломаных, аппроксимирующих оптимальные траектории, и чебышевского центра массива векторов, задающих направление сдвига точки.
Предложенные алгоритмы частично обоснованы и реализованы в виде программного комплекса. Многократный запуск вычислительного комплекса при различных начальных условиях, сгенерированных стохастическим методами, обеспечивает радиус кругов покрытия, достаточно близкий к максимально возможному. Благодарности
Работа была выполнена при финансовой поддержке РФФИ (проект №16-31-00356-мол_а) и комплексной программы фундаментальных исследований УрО РАН, проект №15-16-1-13. Список литературы [25] E. D. Moskalensky. On detecting a wavefront described by a 2D eikonal equation when the velocity in the medium depends on one spatial variable. Numer. Analys. Appl., 3(52): 52–58, 2010.
Iterative algorithms inhomogeneous metrics for optimal packing construction
The problem of packing of equal circles in the convex bounded 2-D sets is considered. The metric is significantly different from the Euclidean one. Here the distance between points is equal to the minimal time that requires for passing from one point to another. In other words, the shortest route between two points is a curve, to spend the least time. The optimality criterion for the packing is the radius of a fix number of circles. The proposed algorithm includes the computational method for constructing boundaries of packing circles as wave fronts, based on principles of geometric optics. To maximize the radius, we use the iterative procedures that simulate the repulsion of circle centers from the boundaries of adjacent packing elements and from the boundary of a convex set. They based on the Chebyshev center constructions, which make it possible to form a displacement vector in the required direction. Numerical modeling for the sets of different geometries and for the different distribution of wave propagation velocities is carried out. The results are visualized.