4488
правок
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) м (→Применение) |
||
Строка 61: | Строка 61: | ||
== Применение == | == Применение == | ||
Далее размерность d будет считаться константной. Декомпозиция на значительно удаленные пары может эффективно применяться для решения задач о близости на в пространстве <math>\mathbb{R}^d</math>. | Далее размерность d будет считаться константной. Декомпозиция на значительно удаленные пары может эффективно применяться для решения задач о близости на точках в пространстве <math>\mathbb{R}^d</math>. | ||
Строка 67: | Строка 67: | ||
И в самом деле, пусть <math>q \in S \;</math> – ближайший сосед точки <math>p \in S \;</math>. Можно построить декомпозицию S на значительно удаленные пары относительно коэффициента удаленности s > 2 за время O(n log n). Пусть <math>(A_i, B_i) \;</math> – пара, в которой <math>p \in A_i \;</math> и <math>q \in B_i \;</math>. Если бы в <math>A_i \;</math> имелась другая точка <math>p' \;</math> из множества S, имело бы место соотношение <math>|pp'| \le 2/s \cdot |pq| < |pq|</math>, что невозможно. Следовательно, <math>A_i \;</math> является одноэлементным множеством. Если (p, q) является парой ближайших точек в S, то множество <math>B_i \;</math> тоже должно быть одноэлементным. Таким образом, пару ближайших точек можно найти | И в самом деле, пусть <math>q \in S \;</math> – ближайший сосед точки <math>p \in S \;</math>. Можно построить декомпозицию S на значительно удаленные пары относительно коэффициента удаленности s > 2 за время O(n log n). Пусть <math>(A_i, B_i) \;</math> – пара, в которой <math>p \in A_i \;</math> и <math>q \in B_i \;</math>. Если бы в <math>A_i \;</math> имелась другая точка <math>p' \;</math> из множества S, имело бы место соотношение <math>|pp'| \le 2/s \cdot |pq| < |pq|</math>, что невозможно. Следовательно, <math>A_i \;</math> является одноэлементным множеством. Если (p, q) является парой ближайших точек в S, то множество <math>B_i \;</math> тоже должно быть одноэлементным. Таким образом, пару ближайших точек можно найти путем рассмотрения всех пар одноэлементных множеств среди O(n) пар, входящих в декомпозицию на значительно удаленные пары. | ||
При помощи следующих действий можно получить более | При помощи следующих действий можно получить более общий результат. | ||
Строка 76: | Строка 76: | ||
В случае размерности d = 2 для решения этих задач обычно используется | В случае размерности d = 2 для решения этих задач обычно используется [[Voronoi diagram|диаграмма Вороного]]. Но для более высоких измерений намного практичнее использовать декомпозицию на значительно удаленные пары, поскольку сложность диаграммы Вороного для n точек может достигать <math>n^{\lfloor d/2 \rfloor} \;</math>. | ||
правок