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

EMST 25 случайных точек на плоскости

Евклидово минимальное остовное дерево (англ. Euclidean minimum spanning tree, EMST) — это минимальное остовное дерево набора из n точек на плоскости (или более обще, в $\mathbb {R} ^{d}$), где вес ребра между любой парой точек является евклидовым расстоянием между двумя точками. Простыми терминами, EMST связывает набор точек с помощью отрезков так, что общая длина всех отрезков минимальна и любая точка может быть достигнута из другой точки по этим отрезкам.

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

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

Нижняя граница

Асимптотическая нижняя граница Ω(n log n) для временной сложности задачи EMST может быть установлена в ограниченных моделях вычисления, так как алгебраическое дерево решений и модели алгебраического дерева решений, в которых алгоритм имеет доступ к входным точкам только через определённые ограниченные примитивы, которые осуществляют простые алгебраические вычисления над координатами. В этих моделях задача о паре ближайших точек требует время $\Omega (n\log n)$, но ближайшая пара будет обязательно ребром EMST, так что EMST также требует такого количества времени . Однако, если входные точки имеют целочисленные координаты и доступны битовые операции и индексация таблицы над координатами, то возможны более быстрые алгоритмы.

Алгоритмы вычисления EMST на плоскости

Наиболее простой алгоритм поиска EMST в двухмерном пространстве, если дано n точек, заключается в построении полного графа с n вершинами, который имеет n(n-1)/2 рёбер, вычисления веса каждого ребра путём нахождения расстояний между каждой парой точек, а затем выполнения стандартного алгоритма поиска минимального остовного дерева (такого как версия алгоритма Прима или алгоритма Краскала) на этом графе. Поскольку этот граф имеет Θ(n²) рёбер для n различных точек, построение графа требует уже времени Ω(n²). Решение задачи требует также пространство размера $\Omega (n^{2})$ для хранения всех рёбер.

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

Поддеревья триангуляции Делоне

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

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 не принадлежит никакому EMST.

Ожидаемый размер

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

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

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

Приложения

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

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

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

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