Прямолинейное остовное дерево: различия между версиями

Доказательство. Чтобы показать, что разбиение обладает свойством единственности, необходимо доказать, что каждая область разбиения обладает этим свойством. Поскольку области <math>R_1 - R_8 \;</math> аналогичны друг другу, достаточно будет доказать это для области <math>R_1 \;</math>.

Точки в области <math>R_1 \;</math> можно охарактеризовать следующими неравенствами: <math>x \ge x_s; \; x - y < x_s - y_s</math>.

Предположим, что имеются точки p и q в <math>R_1 \;</math>. Без потери общности будем считать, что <math>x_p \le x_q \;</math>. Если <math>y_p \le y_q \;</math>, то ||sq|| = ||sp|| + ||pq|| > ||pq||. Следовательно, необходимо рассмотреть только случай <math>y_p > y_q \;</math>. В этом случае <math>||pq|| = |x_p - x_q| + |y_p - y_q| = x_q - x_p + y_p - y_q = (x_q - y_q) + y_p - x_p < (x_s - y_s) + y_p - x_s = y_p - y_s \le x_p - x_s + y_p - y_s = ||sp||</math>.

Пусть даны две точки p, q в одном и том же сегменте (октанте) восьмиугольного разбиения плоскости относительно точки s. Согласно свойству единственности, ||pq|| < max(||sp||; ||sq||). Рассмотрим цикл с точками s, p и q. Согласно свойству циклов, только одну точку с минимальным расстоянием до s необходимо соединить с s. Интересное свойство восьмиугольного разбиения заключается в том, что контур равноудаленных от s точек формирует отрезок прямой в каждой области. В областях <math>R_1, R_2, R_5, R_6 \;</math> эти сегменты описываются уравнением вида x + y = c; в областях <math>R_3, R_4, R_7, R_8 \;</math> – уравнением вида x - y = c.

Для каждой точки s необходимо найти ближайшего к ней соседа в каждом октанте. Опишем, как эффективно вычислить соседей в октанте <math>R_1 \;</math> для всех точек. Случаи остальных октантов симметричны. Для октанта <math>R_1 \;</math> алгоритм с заметающей прямой исполняется для всех точек в порядке неубывания x + y. В процессе заметания поддерживается [[активное множество]], состоящее из точек, для которых ближайшие соседи в <math>R_1 \;</math> еще не найдены. После обработки точки p будут найдены все точки активного множества, содержащие p в их областях <math>R_1 \;</math>. Если такая точка содержится в активном множестве, то, поскольку точки проверяются в порядке неубывания x + y, p должна быть ближайшей точкой для s в <math>R_1 \;</math>.  

Таким образом, будет добавлено ребро sp и точка s будет удалена из активного множества. После обработки этих активных точек точка p будет добавлена в активное множество. Каждая точка будет добавлена в активное множество и удалена из него только один раз.