WikiDer > Кинетическое евклидово минимальное остовное дерево

Kinetic Euclidean minimum spanning tree

А кинетическое евклидово минимальное остовное дерево это кинетическая структура данных который поддерживает Евклидово минимальное остовное дерево (ЕМСТ) набора п из п точки, которые непрерывно движутся.

За набор очков п в 2-мерном пространстве есть два кинетических алгоритма для обслуживания EMST.

Рахмати и Зарей[1] построить кинетическую структуру данных на основе кинетическая триангуляция Делоне для обработки обновлений EMST в время полилога за событие. Их кинетическая структура данных обрабатывает событий, где m - количество всех изменений триангуляции Делоне движущихся точек. Их кинетический подход может хорошо работать для поддержания минимальное остовное дерево (MST) планарный граф чьи веса ребер изменяются как непрерывная функция времени.

Абам, Рахмати и Зарей[2] обеспечивают значительное улучшение точного кинетического поддержания на Евклидово минимальное остовное дерево. Их кинетическая структура данных обрабатывает почти кубическое количество событий.

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

  1. ^ Рахмати, Захед; Зарей, Алиреза (2012). «Кинетическое евклидово минимальное остовное дерево на плоскости». Журнал дискретных алгоритмов. 16: 2–11. Дои:10.1016 / j.jda.2012.04.009.
  2. ^ Али Абам, Мохаммед; Рахмати, Захед; Зарей, Алиреза (2012). «Кинетический граф Пи-Делоне и его приложения». Теория алгоритмов - SWAT. 2012: 48–58. Дои:10.1007/978-3-642-31155-0_5.