Разложение хорошо разделенных пар - Well-separated pair decomposition - Wikipedia

В вычислительная геометрия, а разложение хорошо разделенных пар (WSPD) набора точек ${\displaystyle S\subset \mathbb {R} ^{d}}$, представляет собой последовательность пар множеств ${\displaystyle (A_{i},B_{i})}$, такая, что каждая пара хорошо отделенный, и для каждых двух различных точек ${\displaystyle p,q\in S}$, существует ровно одна пара, разделяющая их.

Граф, индуцированный хорошо разделенным парным разложением, может служить гаечный ключ из полный Евклидов граф, и полезен при приближении решения нескольких проблем, связанных с этим.^[1]

Определение

Визуальное представление хорошо разделенной пары

Позволять ${\displaystyle A,B}$ - два непересекающихся множества точек в ${\displaystyle \mathbb {R} ^{d}}$, ${\displaystyle R(X)}$ обозначить выровненная по оси минимальная ограничивающая рамка для точек в ${\displaystyle X}$, и ${\displaystyle s>0}$ обозначить коэффициент разделения.

Мы считаем ${\displaystyle A}$ и ${\displaystyle B}$ быть хорошо отделенный, если для каждого из ${\displaystyle R(A)}$ и ${\displaystyle R(B)}$ существует d-мяч радиуса ${\displaystyle \rho }$ содержащие его, так что между двумя сферами минимальное расстояние не менее ${\displaystyle s\rho }$.^[2]

Мы рассматриваем последовательность хорошо разделенных пар подмножеств ${\displaystyle S}$, ${\displaystyle (A_{1},B_{1}),(A_{2},B_{2}),\ldots ,(A_{m},B_{m})}$ быть разложение хорошо разделенных пар (WSPD) из ${\displaystyle S}$ если для любых двух различных точек ${\displaystyle p,q\in S}$, существует ровно один ${\displaystyle i}$, ${\displaystyle 1\leq i\leq m}$, так что либо

• ${\displaystyle p\in A_{i}}$ и ${\displaystyle q\in B_{i}}$, или же
• ${\displaystyle q\in A_{i}}$ и ${\displaystyle p\in B_{i}}$.^[1]

Строительство

Разделить дерево

Путем построения ярмарка расколотое дерево, можно построить WSPD размером ${\displaystyle O(s^{d}n)}$ в ${\displaystyle O(n\lg n)}$ время.^[2]

Общий принцип разбиения дерева набора точек S что каждый узел ты дерева представляет собой набор точек S_ты и что ограничивающая рамка R (S_ты) из S_ты делится по своей длинной стороне на две равные части, которые образуют двух дочерних элементов ты и их набор точек. Это делается рекурсивно до тех пор, пока в наборе не останется только одна точка.

Позволять L_{Максимум}(R (X)) обозначают размер самого длинного интервала ограничивающего гипер прямоугольника множества точек Икс и разреши L_я(R (X)) обозначают размер я-я размерность ограничивающего гипер прямоугольника множества точек Икс. Ниже мы приводим псевдокод для вычисления дерева расщепления.

SplitTree (S)    Позволять ты быть узлом для S    если | S | = 1        R (u): = R (S) // R (S) - гипер прямоугольник, каждая сторона которого равна нулю. Хранить в ты единственная точка в S. еще        Вычислить R (S)        Пусть я-е измерение будет тем, где LМаксимум(R (S)) = Lя(R (S))        Расколоть R (S) вдоль я-го измерения в двух гипер прямоугольниках одинакового размера и возьмите точки, содержащиеся в этих гипер прямоугольниках, чтобы сформировать два набора Sv и Sш.        v: = SplitTree (Sv)        w: = SplitTree (Sш)        Магазин v и ш как, соответственно, левый и правый потомки ты.        R (u): = R (S)    возвращаться ты

Этот алгоритм работает в ${\displaystyle O(n^{2})}$ время.

Мы даем более эффективный алгоритм, который работает в ${\displaystyle O(n\lg n)}$ время ниже. Цель состоит в том, чтобы перебрать список только за ${\displaystyle O(n)}$ операций на шаг рекурсии, но каждый раз вызывает рекурсию не более чем в половине точек.

Позволять S_я^j быть j-я координата я-я точка в S такой, что S сортируется по каждому измерению и p (S_я^j) быть точкой. Кроме того, пусть ч (R (S)) быть гиперплоскостью, которая разделяет самую длинную сторону R (S) в двоем. Вот алгоритм в псевдокоде:

SplitTree (S, u)    если | S | = 1        R (u): = R (S) // R (S) - гипер прямоугольник, каждая сторона которого равна нулю. Хранить в ты единственный момент в S.    еще        размер: = | S |        повторение            Вычислить R (S)            R (u): = R (S)            j: = 1            k: = | S |            Пусть я-е измерение будет тем, где LМаксимум(R (S)) = Lя(R (S))            Sv : = ∅            Sш : = ∅            пока Sяj + 1  и Sяк-1 > h (R (S))                размер: = размер - 1                Sv : = Sv ∪ {p (S_i ^ j)}                Sш : = Sш ∪ {p (S_i ^ k)}                j: = j + 1                к: = к - 1                        Позволять v и ш быть соответственно левым и правым потомками ты.            если Sяj + 1 > h (R (S))                Sш : = S  Sv                u: = w                S: = Sш                SplitTree (Sv, v)            иначе если Sяк-1                 Sv : = S  Sш                u: = v                S: = Sv                SplitTree (Sш, w)        до того как размер ≤п⁄2        SplitTree (S, u)

Чтобы иметь возможность поддерживать отсортированные списки для каждого узла, используются связанные списки. Перекрестные указатели сохраняются для каждого списка для других, чтобы иметь возможность извлекать точку за постоянное время. В приведенном выше алгоритме на каждой итерации цикла выполняется вызов рекурсии. На самом деле, чтобы восстановить список без дополнительных затрат на пересбор точек, необходимо перестроить отсортированные списки после того, как все точки будут назначены их узлам. Чтобы выполнить перестройку, пройдите по каждому списку для каждого измерения, добавьте каждую точку в соответствующий список ее узлов и добавьте перекрестные указатели в исходный список, чтобы иметь возможность добавлять перекрестные указатели для новых списков. Наконец, вызовите рекурсию для каждого узла и его набора.

Расчет WSPD

Визуальное представление хорошо разделенной пары, вычисленной с помощью ограничивающих рамок

WSPD можно извлечь из такого разбитого дерева, вызвав рекурсивный Найти пары (v, w) функция на детей каждый узел в разбитом дереве. Позволять ты_л / ты_р обозначают потомков узла ты. Мы даем псевдокод для FindWSPD (T, s) функция ниже.

FindWSPD (T, s)    для каждого узел ты Это не лист в расколотом дереве Т делать        FindPairs (uлтыр)

Мы даем псевдокод для Найти пары (v, w) функция ниже.

Найти пары (v, w)    если Sv и Sш хорошо разделены по s         отчет пара (Sv, Sш)    еще        если( LМаксимум(R (v)) ≤ LМаксимум(R (ш)) ) Рекурсивно вызывать FindPairs (v, wл) и FindPairs (v, wр)        еще            Рекурсивно вызывать Найти пары (vл, w) и Найти пары (vр, w)

Объединение s-хорошо отделенные пары от всех звонков Найти пары (v, w) дает WSPD для разделения s.

Доказательство правильности алгоритма

Ясно, что пары, возвращаемые алгоритмом, хорошо разделены из-за условия возврата функции FindPairs. Теперь нам нужно доказать, что для любых различных точек ${\displaystyle p}$ и ${\displaystyle q}$ в ${\displaystyle S}$, есть уникальная пара ${\displaystyle \{A,B\}}$ так что я) ${\displaystyle p\in A}$ и ${\displaystyle q\in B}$ или (ii) ${\displaystyle p\in B}$ и ${\displaystyle q\in A}$. Без ограничения общности предположим, что выполнено (i). Позволять ${\displaystyle u}$ быть самым низким общим предком ${\displaystyle p}$ и ${\displaystyle q}$ в расколотом дереве и пусть ${\displaystyle v}$ и ${\displaystyle w}$ быть детьми ${\displaystyle u}$. В силу последнего предположения ${\displaystyle p}$ находится в поддереве ${\displaystyle v}$ и ${\displaystyle q}$ в поддереве ${\displaystyle w}$. Звонок в Найти пары (v, w) обязательно делается в FindWSPD. Поскольку каждый раз, когда происходит рекурсия, дерево рекурсии создает две ветви, которые содержат все точки текущего вызова рекурсии, будет последовательность вызовов FindPairs приводит к ${\displaystyle p}$ в ${\displaystyle A}$ и ${\displaystyle q}$ в ${\displaystyle B}$. Потому что ${\displaystyle u}$ является самым низким общим предком ${\displaystyle p}$ и ${\displaystyle q}$, звоню FindPairs на дочерних элементах более высокого узла приведет к ${\displaystyle p}$ и ${\displaystyle q}$ не в паре и звоню FindPairs на потомках в одном из узлов одного из поддеревьев ${\displaystyle u}$ приведет к ${\displaystyle p}$ или же ${\displaystyle q}$ не входя ни в одну пару. Таким образом, пара ${\displaystyle \{A,B\}}$ единственный, разделяющий ${\displaystyle p}$ и ${\displaystyle q}$.

Каждый раз, когда дерево рекурсии разделяется на две части, к разложению добавляется еще одна пара. Итак, время выполнения алгоритма определяется количеством пар в окончательной декомпозиции.

Каллахан и Косараджу доказали, что этот алгоритм находит хорошо разделенное парное разложение (WSPD) размера ${\displaystyle O(s^{d}n)}$.^[2]

Характеристики

Лемма 1.: Позволять ${\displaystyle \{A,B\}}$ быть хорошо разделенной парой относительно ${\displaystyle s}$. Позволять ${\displaystyle p,p'\in A}$ и ${\displaystyle q\in B}$. Потом, ${\displaystyle |pp'|\leq (2/s)|pq|}$.

Доказательство: Потому что ${\displaystyle p}$ и ${\displaystyle p'}$ находятся в одном наборе, мы имеем ${\displaystyle |pp'|\leq 2\rho }$ куда ${\displaystyle \rho }$ - радиус окружности ${\displaystyle A}$ и ${\displaystyle B}$. Потому что ${\displaystyle p}$ и ${\displaystyle q}$ находятся в двух хорошо разделенных наборах, мы имеем ${\displaystyle |pq|\geq s\rho }$. Получаем, что:

${\displaystyle {\begin{aligned}&{\frac {|pp'|}{2}}\leq \rho \leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&{\frac {|pp'|}{2}}\leq {\frac {|pq|}{s}}\\\Leftrightarrow &\\&|pp'|\leq {\frac {2}{s}}|pq|\\\end{aligned}}}$

Лемма 2: Позволять ${\displaystyle \{A,B\}}$ быть хорошо разделенной парой относительно ${\displaystyle s}$. Позволять ${\displaystyle p,p'\in A}$ и ${\displaystyle q,q'\in B}$. Потом, ${\displaystyle |p'q'|\leq (1+4/s)|pq|}$.

Доказательство: По неравенству треугольника имеем:

${\displaystyle |p'q'|\leq |p'p|+|pq|+|qq'|}$

Из леммы 1 получаем:

${\displaystyle {\begin{aligned}|p'q'|&\leq (2/s)|pq|+|pq|+(2/s)|pq|\\&=(1+4/s)|pq|\end{aligned}}}$

Приложения

Разложение на хорошо разделенные пары имеет применение при решении ряда задач. WSPD можно использовать для:

• Решить проблема ближайшей пары в ${\displaystyle O(n\lg n)}$ время.^[1]
• Решить kпроблема ближайших пар в ${\displaystyle O(n\lg n+k)}$ время.^[1]
• Решить k-ближайшая парная задача в ${\displaystyle O(n\lg n)}$ время.^[3]
• Решить проблема всех ближайших соседей в ${\displaystyle O(n\lg n)}$ время.^[1]
• Обеспечить ${\displaystyle (1-\epsilon )}$-приближение из диаметр точки, установленной в ${\displaystyle O(n\lg n)}$ время.^[1]
• Непосредственно вызвать гаечный ключ набора точек.^[1]
• Обеспечьте t-приближение Евклидово минимальное остовное дерево в d размеры в ${\displaystyle O(n\lg n)}$ время.^[1]
• Обеспечить ${\displaystyle (1+\epsilon )}$-аппроксимация Евклидово минимальное остовное дерево в d размеры в ${\displaystyle O(n\lg n+(\epsilon ^{-2}\lg ^{2}{\frac {1}{\epsilon }})n)}$ время.^[4]

Рекомендации

1. Смид, Мишель (16 августа 2005 г.). «Разложение хорошо разделенных пар и его приложения» (PDF). Получено 26 марта 2014.
2. Каллахан, П. Б. и Косараджу, С. Р. (январь 1995 г.). «Разложение многомерных наборов точек с приложениями к k-ближайшим соседям и n-частным потенциальным полям». Журнал ACM. 42 (1): 67–90. Дои:10.1145/200836.200853.
3. Беспамятных, Сергей; Сигал, Майкл (2002). «Быстрые алгоритмы приближения расстояний». Алгоритмика. 33 (2): 263–269. Дои:10.1007 / s00453-001-0114-7.
4. Арья, Сунил; Маунт, Дэвид М. (2016). «Быстрый и простой алгоритм для вычисления приблизительного евклидова минимального остовного дерева». Материалы двадцать седьмого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам.