Евклидово минимальное остовное дерево

Евклидово минимальное остовное дерево или EMST - это минимальное остовное дерево из набора из n точек в плоскости (или, в более общем смысле, в ℝ), где вес ребра между каждой парой points - это евклидово расстояние между этими двумя точками. Проще говоря, EMST соединяет набор точек с помощью линий, так что общая длина всех линий минимизируется, и любая точка может быть достигнута из любой другой, следуя линиям.

На плоскости EMST для данного набора точек может быть найден за Θ (n log n) время, используя пространство O (n) в алгебраическом дереве решений модель вычисления. Более быстрые рандомизированные алгоритмы сложности O (n log log n) известны в более мощных моделях вычислений, которые более точно моделируют возможности реальных компьютеров.

В более высоких измерениях (d ≥ 3) поиск оптимального алгоритма остается открытой проблемой.

• 1 Нижняя граница
• 2 Алгоритмы для вычисления EMST в двух измерениях
• 3 Высокие измерения
• 4 Поддерево триангуляции Делоне
• 5 Ожидаемый размер
• 6 Приложения
• 7 Планарная реализация
• 8 См. Также
• 9 Ссылки

Асимптотическая нижняя граница Ω (n log n) для временной сложности задачи EMST может быть установлена ​​в ограниченных моделях вычислений, таких как алгебраическое дерево решений и в моделях, в которых алгоритм имеет доступ к входным точкам только через определенные ограниченные примитивы, которые выполняют простые алгебраические вычисления над своими координатами: в этих моделях задача ближайшей пары точек требует времени Ω (n log n), но cl Пара osest обязательно является краем EMST, поэтому EMST также требует столько времени. Однако, если входные точки имеют целочисленные координаты и побитовые операции и операции индексации таблиц разрешены с использованием этих координат, тогда возможны более быстрые алгоритмы.

Простейший алгоритм для поиска EMST в двух измерениях с учетом n точек состоит в том, чтобы фактически построить полный граф на n вершинах, который имеет n (n-1) / 2 ребра, вычислите вес каждого ребра, найдя расстояние между каждой парой точек, а затем запустите стандартный алгоритм минимального остовного дерева (например, версию алгоритма Прима или алгоритма Крускала ) в теме. Поскольку этот граф имеет Θ (n) ребер для n различных точек, его построение уже требует Ω (n) времени. Это решение также требует пространства Ω (n) для хранения всех ребер.

Лучший подход к поиску EMST на плоскости - отметить, что это подграф каждой триангуляции Делоне из n точек, значительно сокращенный набор ребер:

1. Вычислите триангуляцию Делоне за O (n log n) время и O (n) пространство. Поскольку триангуляция Делоне является плоским графом, а количество ребер не более чем в три раза превышает количество вершин в любом плоском графе, это генерирует только O (n) ребер.
2. Обозначьте каждое из них ребро с его длиной.
3. Запустите алгоритм минимального остовного дерева графа на этом графе, чтобы найти минимальное остовное дерево. Поскольку существует O (n) ребер, для этого требуется время O (n log n) с использованием любого из стандартных алгоритмов минимального связующего дерева, таких как алгоритм Борувки, алгоритм Прима или Алгоритм Крускала.

Конечным результатом является алгоритм, занимающий O (n log n) времени и O (n) пространства.

Если входные координаты являются целыми числами и могут использоваться как индексы массива, возможны более быстрые алгоритмы: триангуляция Делоне может быть построена с помощью рандомизированного алгоритма в O ( n log log n) ожидаемое время. Кроме того, поскольку триангуляция Делоне является плоским графом, ее минимальное остовное дерево может быть найдено за линейное время с помощью варианта алгоритма Борувки, который удаляет все ребра, кроме самых дешевых, между каждой парой компоненты после каждого этапа алгоритма. Следовательно, общее ожидаемое время для этого алгоритма составляет O (n log log n).

Проблема также может быть обобщена на n точек в d-мерном пространстве ℝ. В более высоких измерениях связность, определяемая триангуляцией Делоне (которая аналогичным образом разделяет выпуклую оболочку на d-мерные симплексы ), содержит минимальное остовное дерево; однако триангуляция может содержать полный граф. Следовательно, поиск евклидова минимального остовного дерева как остовного дерева полного графа или как остовного дерева триангуляции Делоне занимает время O (dn). Для трех измерений можно найти минимальное остовное дерево за время O ((n log n)), а в любом измерении, превышающем три, можно решить его за время, которое быстрее, чем квадратичная временная граница для полного граф и алгоритмы триангуляции Делоне. Для равномерно случайных наборов точек можно вычислить минимальные остовные деревья так же быстро, как и сортировку. Используя разложение на хорошо разделенные пары, можно получить (1 + ε) -аппроксимацию за время O (n log n).

Все ребра EMST - это ребра графа относительных окрестностей, которые, в свою очередь, являются ребрами графа Габриэля, которые являются ребрами в триангуляции Делоне точек, что может быть доказано с помощью эквивалентного контрапозитивного утверждения: каждое ребро, не входящее в триангуляцию Делоне, также не входит ни в какой EMST. Доказательство основано на двух свойствах минимальных остовных деревьев и триангуляции Делоне:

1. (свойство цикла минимальных остовных деревьев): для любого цикла C в графе, если вес ребра e равен C больше, чем веса других ребер C, то это ребро не может принадлежать MST.
2. (свойство триангуляций Делоне): если есть окружность с двумя входными точками на ее границе, которая не содержит других входных точек, линия между этими двумя точками является ребром каждой триангуляции Делоне.

Рассмотрим ребро e между двумя входными точками p и q, которое не является ребром триангуляции Делоне. Свойство 2 означает, что окружность C с диаметром e должна содержать другую точку r внутри. Но тогда r ближе к p и q, чем они друг к другу, и поэтому ребро от p до q является самым длинным ребром в цикле точек p → q → r → p, и по свойству 1 e не входит в любой EMST.

Ожидаемый размер EMST для большого количества точек был определен J. Майкл Стил. Если $f\; \{\backslash \; displaystyle\; f\}$- это плотность функции вероятности для выбора точек, то для больших $n\; \{\backslash \; displaystyle\; n\}$и $d\; \ne \; 1\; \{\backslash \; displaystyle\; d\; \backslash \; neq\; 1\}$размер ЕМТ примерно

$c\; (d)\; nd\; -\; 1\; d\; \int \; R\; df\; (x)\; d\; -\; 1\; ddx\; \{\backslash \; displaystyle\; c\; (d)\; n\; ^\; \{\backslash \; frac\; \{d-1\}\; \{d\}\}\; \backslash \; int\; \_\; \{\backslash \; mathbb\; \{R\}\; ^\; \{d\}\}\; f\; (x)\; ^\; \{\backslash \; frac\; \{d-1\}\; \{d\}\}\; dx\}$

где $c\; (d)\; \{\backslash \; displaystyle\; c\; (d)\}$- константа, зависящая только от измерения $d\; \{\backslash \; displaystyle\; d\}$. Точные значения констант неизвестны, но могут быть оценены на основании эмпирических данных.

Очевидным применением евклидовых минимальных остовных деревьев является поиск самой дешевой сети из проводов или труб для соединения набора точек, предполагая, что ссылки стоят фиксированную сумму за единицу длины. Однако, хотя они дают абсолютную нижнюю границу необходимого количества подключений, большинство таких сетей предпочитают k-связанный граф дереву, так что отказ любого отдельного канала не разбивает сеть на части..

Другое применение EMST - это алгоритм аппроксимации постоянного множителя для приближенного решения евклидовой задачи коммивояжера, версии задачи коммивояжера на множестве точек на плоскости с обозначенными длинами ребер. Этот реалистичный вариант задачи может быть решен с коэффициентом 2 путем вычисления EMST, выполнения обхода по его границе, которая очерчивает все дерево, а затем удаления всех, кроме одного вхождения каждой вершины из этого обхода.

Задача реализации для евклидовых минимальных остовных деревьев формулируется следующим образом: для дерева T = (V, E) найти местоположение D (u) для каждой вершины u ∈ V так, чтобы T было минимальным остовным деревом D (u): u ∈ V, или определить, что таких местоположений не существует. Проверка существования реализации в плоскости является NP-сложной.

• Прямолинейное минимальное остовное дерево

1. ^ Бучин, Кевин; Мульцер, Вольфганг (2009). Триангуляции Делоне за время O (sort (n)) и более (PDF). Proc. 50-й симпозиум IEEE по основам компьютерных наук. С. 139–148. doi : 10.1109 / FOCS.2009.53..
2. ^Яо, A.C.-C. (1989), «Нижние оценки для деревьев алгебраических вычислений с целочисленными входами», Proc. 30-й ежегодный симпозиум по основам компьютерных наук (FOCS 1989), стр. 308–313, doi : 10.1109 / SFCS.1989.63495.
3. ^Дэвид Эппштейн (1999), «Балки и гаечные ключи», в Sack, J.-R. ; Уррутия, Дж. (ред.), Справочник по вычислительной геометрии, Elsevier, стр. 425–461 ; Мареш, Мартин (2004), «Два алгоритма линейного времени для MST на минорном замкнутом классы графов » (PDF), Archivum mathematicum, 40 (3): 315–320.
4. ^ Agarwal, PK ; Эдельсбруннер, Х. ; Schwarzkopf, O.; Велцль, Э. (1991), «Евклидовы минимальные остовные деревья и бихроматические ближайшие пары», Дискретная и вычислительная геометрия, Springer, 6 (1): 407–422, doi : 10.1007 / BF02574698.
5. ^Chatterjee, S.; Коннор, М.; Кумар, П. (2010), «Геометрические минимальные остовные деревья с GeoFilterKruskal», в Фесте, Паола (ред.), Симпозиум по экспериментальным алгоритмам, Конспект лекций по информатике, 6049, Springer-Verlag, стр. 486–500, doi : 10.1007 / 978-3-642-13193-6_41.
6. ^Смид, Майкл (16 августа 2005 г.). «Разложение хорошо разделенных пар и его приложения» (PDF). Проверено 26 марта 2014 г.
7. ^Ежи В. Яромчик и Годфрид Т. Туссен, «Графики относительного соседства и их родственники», Proceedings of the IEEE, Vol. 80, No. 9, сентябрь 1992 г., стр. 1502–1517.
8. ^Годфрид Т. Туссен, "Комментарий к алгоритмам для вычисления графа относительных окрестностей", Electronics Letters, Vol. 16, No. 22, October 1981, pp. 860–861.
9. ^Годфрид Т. Туссен, "Граф относительной окрестности конечного плоского множества", Распознавание образов, Vol. 12. 1980. С. 261–268.
10. ^Роберт Плесс. Лекция 17: Диаграммы Вороного и триангуляции Делоне. Весна 2003 г., страница класса вычислительной геометрии. Адъюнкт-профессор компьютерных наук и инженерии Вашингтонского университета. http://www.cs.wustl.edu/~pless/506/l17.html Архивировано 12 сентября 2006 г. на Wayback Machine
11. ^Роберт Седжвик и Кевин Уэйн. Минимальные конспекты лекций по связующему дереву. Компьютерные науки 226: алгоритмы и структуры данных, весна 2007 г., Принстонский университет. http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/19MST.pdf
12. ^Стил, Дж. Майкл (1988). «Темпы роста евклидовых минимальных остовных деревьев со степенно взвешенными ребрами» (PDF). Летопись вероятности. 16 (4): 1767–1787. doi : 10.1214 / aop / 1176991596.
13. ^Идс, Питер ; Whitesides, Sue (1994), "Проблема реализации евклидовых минимальных остовных деревьев NP-трудна", Proc. 10-й симпозиум ACM по вычислительной геометрии, стр. 49–56, doi : 10.1145 / 177424.177507.

• Колледж Смита: Проект открытых проблем: Проблема 5: Евклидово минимальное остовное дерево
• Макс. Planck-Institut fuer Informatik: Решения для упражнений, Кавита Теликепалли (Постскриптум)
• СТАНН (Майкл Коннор, Пиюш Кумар и Самид Чаттерджи): библиотека C ++, которая может вычислять евклидовы минимальные остовные деревья в малых размерностях