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

ЕМКД 25 випадкових точок на площині

Евклі́дове мініма́льне кістяко́ве де́рево (ЕМКД; англ. Euclidean minimum spanning tree, EMST) — це мінімальне кістякове дерево набору з n точок на площині (або загальніше, $\mathbb {R} ^{d}$), де вага ребра між будь-якою парою точок є евклідовою відстанню між двома точками. Простими термінами ЕМКД пов'язує набір точок за допомогою відрізків так, що загальна довжина всіх відрізків мінімальна і будь-яку точку можна досягти з іншої точки за цими відрізками.

На площині ЕМКД для даного набору точок можна знайти за час $\Theta (n\log n)$ з використанням простору $O(n)$ при обчисленні моделі алгебричного дерева розв'язків. У сильніших моделях обчислення, які точніше моделюють можливості реальних комп'ютерів, відомі швидші ймовірнісні алгоритми зі складністю $O(n\log \log n)$.

У вищих розмірностях ($d\geqslant 3$) пошук оптимального алгоритму залишається відкритою проблемою.

Нижня межа

Асимптотичну нижню межу $\Omega (n\log n)$ для часової складності задачі ЕМКД можна встановити в обмежених моделях обчислення, таких як алгебричне дерево розв'язків і моделі алгебричного дерева розв'язків, у яких алгоритм має доступ до вхідних точок тільки через певні обмежені примітиви, які здійснюють прості алгебричні обчислення над координатами. У цих моделях задача про пару найближчих точок потребує часу $\Omega (n\log n)$, але найближча пара обов'язково буде ребром ЕМКД, так що ЕМКД також вимагає такого часу. Однак, якщо вхідні точки мають цілі координати і доступні бітові операції та індексація таблиці над координатами, то можливі швидші алгоритми.

Алгоритми обчислення ЕМКД на площині

Найпростіший алгоритм пошуку ЕМКД у двовимірному просторі, якщо дано n точок, полягає в побудові повного графа з n вершинами, який має n(n -1)/2 ребер, обчислення ваги кожного ребра, тобто, відстаней між кожною парою точок, а потім виконання стандартного алгоритму пошуку мінімального кістякового дерева (такого як версія алгоритму Прима або алгоритму Крускала) на цьому графі. Оскільки цей граф має Θ(n²) ребер для n різних точок, побудова графа вимагає часу Ω(n²). Розв'язання задачі вимагає також простору розміру $\Omega (n^{2})$ для зберігання всіх ребер.

Для досконалішого підходу до пошуку ЕМКД на площині зауважимо, що воно є підграфом будь-якої тріангуляції Делоне 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. У вищих розмірностях зв'язність, визначена тріангуляцією Делоне (яка розбиває опуклу оболонку на d-вимірні симплекси) містить мінімальне кістякове дерево. Проте тріангуляція може містити повний граф. Тому пошук евклідового мінімального кістякового дерева як кістякового дерева повного графа або як кістякового дерева тріангуляцій Делоне вимагатимуть часу $O(dn^{2})$. У тривимірному просторі можна знайти мінімальне кістякове дерево за час $O((n\log n)^{\tfrac {4}{3}})$, а в будь-якому просторі більшої розмірності можна розв'язати задачу швидше, ніж межа з квадратичним часом для повного графа та алгоритмів тріангуляції Делоне. Для рівномірно розподілених випадкових точок можна обчислити мінімальні кістяки з тією ж швидкістю, що й сортування. Використовуючи цілком розділену декомпозицію пар можна отримати $(1+\epsilon )$-апроксимацію за час $O(n\log n)$.

Піддерева тріангуляції Делоне

Всі ребра ЕМКД є ребрами графа відносних околів, які, у свою чергу, є ребрами графа Габріеля, які є ребрами в тріангуляції Делоне точок, що можна довести через контрапозитивний еквівалент твердження: будь-яке ребро, що не входить до тріангуляції Делоне, не міститься в жодному ЕМКД. Доведення ґрунтується на двох властивостях мінімальних кістяків і тріангуляції Делоне:

1. (властивість циклів мінімальних кістякових дерев): Для будь-якого циклу C у графі, якщо вага ребра e графа C більша від ваги іншого ребра C, це ребро не може належати мінімальному кістяковому дереву.
2. (властивість тріангуляцій Делоне): Якщо є цикл із двома вхідними точками на його межі, який не містить інших вхідних точок, відрізок між цими двома точками є ребром будь-якої тріангуляції Делоне.

Розглянемо ребро e між двома вхідними точками p і q, яке є ребром тріангуляції Делоне. Зі властивості 2 випливає, що цикл C з e як діаметром має містити всередині деяку іншу точку r. Але тоді r розташована ближче як до p, так і до q, ніж вони одна відносно одної, а тому ребро з p в q є найдовшим у циклі точок $p\to q\to r\to p$ і, за властивістю 1, e не належить жодному ЕМКД.

Очікуваний розмір

Очікуваний розмір ЕМКД для великих наборів точок визначив Дж. Міхаель Стіл. Якщо $f$ є густиною функції ймовірності для вибору точок, то для великих $n$ і $d\neq 1$ розмір ЕМКД приблизно дорівнює

$c(d)n^{\frac {d-1}{d}}\int _{\mathbb {R} ^{d}}f(x)^{\frac {d-1}{d}}dx$

де $c(d)$ — стала, яка залежить тільки від розмірності $d$. Точне значення сталої невідоме, але можна оцінити її емпірично.

Застосування

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

Іншим застосуванням ЕМКД є апроксимувальний алгоритм зі сталим множником для наближеного розв'язання евклідової задачі комівояжера, версії задачі комівояжера на множині точок площини з ребрами, ціни яких дорівнюють їх довжині. Цей реалістичний варіант задачі можна розв'язати апроксимаційно зі множником 2, обчисливши ЕМКД, пройшовши вздовж його межі, яка окреслює все дерево, а потім видаливши всі вершини, що зустрілися кратно (залишивши тільки одну).

Планарна реалізація

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

Див. також

• Граф Уркгарта
• Деревний кістяк

Література

• Kevin Buchin, Wolfgang Mulzer. Delaunay triangulations in O(sort(n)) time and more // [1] — 2009. — DOI:10.1109/FOCS.2009.53. Архівовано з джерела 21 січня 2022
• Yao A. C.-C. Lower bounds for algebraic computation trees with integer inputs // Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS 1989). — 1989. — DOI:10.1109/SFCS.1989.63495.
• David Eppstein. Spanning trees and spanners // Handbook of Computational Geometry. — Elsevier, 1999.
• Martin Mareš. Two linear time algorithms for MST on minor closed graph classes // Archivum mathematicum. — 2004. — Т. 40, вип. 3. Архівовано з джерела 9 травня 2009. Процитовано 13 червня 2022.
• Pankaj K. Agarwal, Herbert Edelsbrunner, Schwarzkopf O., Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs // Discrete and Computational Geometry. — Springer, 1991. — Т. 6, вип. 1. — DOI:10.1007/BF02574698.
• Chatterjee S., Connor M., Kumar P. Geometric minimum spanning trees with GeoFilterKruskal // Symposium on Experimental Algorithms / Paola Festa. — Springer-Verlag, 2010. — Т. 6049. — (Lecture Notes in Computer Science) — DOI:10.1007/978-3-642-13193-6_41.
• Michiel Smid. The well-separated pair decomposition and its applications. — 2005. — August. Архівовано з джерела 18 лютого 2022. Процитовано 2014-03-26.
• Jerzy W. Jaromczyk, Godfried T. Toussaint. Relative neighborhood graphs and their relatives // Proceedings of the IEEE. — 1992. — Т. 80.
• Godfried T. Toussaint. Comment on algorithms for computing relative neighborhood graph // Electronics Letters. — 1981. — Т. 16, № 22 (October).
• Godfried T. Toussaint. The relative neighborhood graph of a finite planar set // Pattern Recognition. — 1980. — Т. 12.
• Robert Pless; Associate Professor of Computer Science and Engineering. Lecture 17: Voronoi Diagrams and Delauney Triangulations // [2] — Washington University, 2003. Архівовано з джерела 2 січня 2018
• Robert Sedgewick, Kevin Wayne. Minimum Spanning Tree lecture notes. Computer Science 226: Algorithms & Data Structures. — Princeton University, 2007. Архівовано з джерела 22 травня 2022. Процитовано 13 червня 2022.
• J. Michael Steele. Growth rates of Euclidean minimum spanning trees with power weighted edges // The Annals of Probability. — 1988. — Т. 16, вип. 4. — DOI:10.1214/aop/1176991596. Архівовано з джерела 6 травня 2021. Процитовано 13 червня 2022.
• Peter Eades, Sue Whitesides. The realization problem for Евклидово минимальное остовное дерево s is NP-hard // Proc. 10th ACM Symposium on Computational Geometry. — 1994. — DOI:10.1145/177424.177507.
• Smith College: The Open Problems Project: Problem 5: Euclidean Minimum Spanning Tree [Архівовано 10 грудня 2016 у Wayback Machine.]
• Max-Planck-Institut fuer Informatik: Exercise solutions, by Kavitha Telikepalli (Postscript)
• STANN (Michael Connor, Piyush Kumar and Samidh Chatterjee): C++ библиотека вычисления евклидова минимального остовного дерева в низких размерностях