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

Нотация ||sp|| используется для представления расстояния между s и p согласно метрике L1. Определим ''восьмиугольное разбиение'' плоскости относительно точки s как разбиение, порожденное двумя прямыми линиями под углом 90 градусов и двумя прямыми под углом 45 градусов к ним, как показано на рис. 2a. Здесь каждая из областей, от <math>R_1 \;</math> до <math>R_8 \;</math>, включает только одну из ограничивающих ее полупрямых, как можно видеть на рис. 2b. Можно показать, что восьмиугольное разбиение обладает свойством единственности.

Рис. 1.

Восьмиугольное разбиение и свойство единственности

Для каждой точки 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>.