Минимальные геометрические остовные деревья: различия между версиями

Ближайших лидеров для любого заданного лидера можно эффективно найти при помощи техники группировки и структур данных для динамического опроса ближайших пар[ ], а также дополнительных фиктивных точек, которые можно вставлять и удалять в исследовательских целях в различных небольших блоках на расстоянии O(l) от лидера. Для сохранения инварианта при переходе к последующим фазам количество лидеров соответствующим образом сокращается, по мере того как пары близлежащих групп объединяются в единые группы. Для рассмотрения правильных типов пар также необходимо организовывать группы в зависимости от различных направлений, на которых могут найтись новые кандидаты – ребра MST, смежные с вершинами группы. Подробнее об этом в работе Кржнарика и коллег [10].

Существует специальная версия алгоритма нахождения бихроматической пары ближайших точек, для которой Кржнарик и коллеги [10] показали, что она имеет ту же временную сложность, что и вычисление MST – она работает для специального случая, когда оба множества красных и синих точек имеют очень небольшой диаметр по сравнению с расстоянием между ближайшей бихроматической парой точек. Это соотношение может быть сделано произвольно малым за счет выбора подходящего значения " в качестве параметра для создания групп и лидеров. Этот факт использовался для выведения более эффективных алгоритмов для трехмерного случая.

К примеру, в метрике L1 возможно за время O(n log n) построить специальную разновидность планарной диаграммы Вороного для синих точек на плоскости, отделяющей синие точки от красных и имеющей следующее свойство: для каждой рассматриваемой точки q в полупространстве, включающем красные точки, можно использовать эту диаграмму Вороного, чтобы за время O(log n) найти синюю точку, ближайшую к q согласно метрике L1. (Можно рассматривать эту планарную диаграмму Вороного как определяемую вертикальными проекциями синих точек на плоскость, содержащую диаграмму, а размер клетки Вороного зависит от расстояния между соответствующей синей точкой и плоскостью). Таким образом, рассматривая последовательно каждую красную точку, можно решить задачу нахождения бихроматической пары ближайших точек для подобных сильно разнесенных красно-синих множеств за полное время O(nlog n).

Используя этот подход, Кржнарик и коллеги [10] показали, как вычислить MST для S за оптимальное время O(n log n) согласно метрикам L1 и L1 в случае, если d = 3. Время исполнения было улучшено по сравнению с ранее известными границами благодаря работам Габова и коллег [9] и Беспамятных [ ], которые доказали, что для d = 3 MST можно вычислить за время O(n log n log log n) согласно метрикам L1 и L1.

Основные результаты Кржнарика и коллег [ ] можно изложить в следующей теореме.

Теорема. В модели алгебраического дерева вычислений для любой фиксированной Lp-метрики и любого фиксированного количества размерностей вычисление MST имеет ту же временную сложность в наихудшем случае, с поправкой на константный множитель, что и вычисление бихроматической пары ближайших точек. Кроме того, в трехмерном пространстве с метриками L1 и L1 задача MST, также как и вычисление бихроматической пары ближайших точек, требуют оптимального времени вычисления O(n log n).