Геометрические остовы: различия между версиями

Пусть A и B – два конечных множества точек в <math>\mathcal{R}^d</math>. Будем называть A и B ''значительно удаленными'' по отношению к вещественному числу s > 0, если существуют два непересекающихся шара <math>C_A \;</math> и <math>C_B \;</math> одного и того же радиуса, такие, что <math>C_A \;</math> содержит A, <math>C_B \;</math> содержит B, а расстояние между <math>C_A \;</math> и <math>C_B \;</math> по меньшей мере в s раз превышает радиус <math>C_A \;</math>. Значение s называется ''коэффициентом удаления''.

'''Определение 1 [6]'''. Пусть S – множество точек в пространстве <math>\mathcal{R}^d \;</math>, а s > 0 – вещественное число. ''Декомпозицией значительно удаленных пар'' (well-separated pair decomposition, WSPD) для S относительно s является последовательность <math>\{ A_i, B_i \} , 1 \le i \le m \;</math>, пар непустых подмножеств S, таких, что:

Декомпозицию значительно удаленных пар разработали Кэллахан и Косарайю [6]. Построение t-остова при помощи этого подхода начинается с построения WSPD-декомпозиции S относительно коэффициента удаления s = (4(t + 1))/(t - 1). Вначале положим остовный граф равным <math>G = (S, \empty) \;</math> и будем итеративно добавлять ребра следующим образом. Для каждой значительно удаленной пары {A, B} из декомпозиции к графу добавляется ребро (a, b), где a и b – произвольные точки из A и B, соответственно. Полученный граф называется WSPD-графом на S.

Алгоритмы построения разреженных остовов получили широкое применение в таких областях, как поиск в метрическом пространстве [1], который включает запрос по содержанию в мультимедийных объектах, текстовый информационный поиск, распознавание образов и аппроксимация функций. Еще одним примером является широковещательная рассылка в сетях коммуникаций [17]. Несколько хорошо известных теоретических работ также основываются на построении t-остовов – к примеру, Рао и Смит [19] совершили прорыв, предложив схему аппроксимации с оптимальным временем O(n log n) для хорошо известной [[Евклидова задача коммивояжера|евклидовой задачи коммивояжера]], основанную на использовании t-остовов (или баньянов). Шумай и Лингас [7] предложили схемы аппроксимации для задач о многосвязности с нахождением объектов минимальной стоимости в геометрических сетях.