10 / 14
стве задачи) областей близости
P
1
, . . . , P
n
(
P
i
⊂
U
d
), т.е. таких мно-
жеств, что расстояние от любой точки
t
⊂
Р
i
до точки
p
i
, не превосхо-
дит расстояния от
t
до
p
j
,
j
6
=
i
. В общем виде можно принять, что на
пространстве
U
d
задана положительно-определенная дистанционная
функция dist (
∙
). В частности, можно, например, полагать, что метрика
индуцируется произвольной нормой в пространстве
U
d
, и тогда соот-
ветствующая дистанционная функция будет симметрична. Отметим,
в частности, что на плоскости для любой метрики
l
q
,
q
= 1
,
2
, . . . ,
∞
,
задача решается за время
O
(
n
log
n
)
.
Обозначим ДВ конфигурации терминальных точек
Р
=
{
р
1
, . . . ,
р
n
}
через
D
(
P
)
. Рассмотрим гиперграф
Н
(
Р
)
, вершинами которого явля-
ются области близости
P
1
, . . . , P
n
, а ребрами — те семейства областей
близости, пересечение которых не пусто, а также пустое множество.
Тем самым гиперграф пересечений
Н
(
Р
)
— гиперграф пересечений
(нерв) семейства множеств и является, по определению, симплици-
альным комплексом.
Определение 1.
Диаграммы Вороного, которым соответствуют
одинаковые комплексы, называются эквивалентными. Использование
этой задачи в описанной выше модели сети мобильного оператора
требует дополнительных уточнений возможных целей.
Цель 1.
Корректно построить алгоритм отнесения пользователя к
точке доступа. Ведь может оказаться так, что при любом сколь угод-
но малом изменении координат пользователя возникает неопределен-
ность в выборе такой точки.
Цель 2.
Необходимо предусмотреть в упомянутом алгоритме воз-
можность выхода из строя любой точки доступа.
Достижение цели 1 может быть обеспечено использованием тео-
рии устойчивости. Сначала определяется факт устойчивости. Для не-
устойчивых конфигураций вводятся дополнительные правила с учетом
координат пользователя. В двух приведенных ниже утверждениях при-
веден пример исследования устойчивости. При этом дополнительные
правила следуют из смысла вводимых ниже параметров.
Пусть близость конфигураций в конфигурационном пространстве
R
d
×
n
задается некоторой нормой. Как было отмечено выше, в общем
случае эта норма никак не связана с дистанционной функцией в ис-
ходном пространстве.
Определение 2.
Диаграмма Вороного конфигурации терминалов
Р
называется устойчивой, если эквивалентны ДВ всех конфигура-
ций в некоторой окрестности конфигурации
Р
в конфигурационном
пространстве. Диаграмма Вороного, которая не является устойчивой,
называется неустойчивой.
Полагается, что устойчивой диаграмме соответствует устойчивая
конфигурация (устойчивое множество терминалов
Р
), а неустойчивой
диаграмме — неустойчивая.
70 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 5