Жадный геометрический гаечный ключ

В вычислительной геометрии жадный геометрический остов — это неориентированный граф , расстояния которого приближаются к евклидовым расстояниям среди конечного набора точек в евклидовом пространстве . Вершины графа представляют эти точки. Ребра остова выбираются жадным алгоритмом , который включает ребро всякий раз, когда его две конечные точки не соединены коротким путем из более коротких ребер. Жадный остов был впервые описан в докторской диссертации Гаутама Даса ^[1] и в статье на конференции ^[2] и в последующей журнальной статье Инго Альтхёфера и др. ^[3] Эти источники также приписывают Маршаллу Берну (неопубликовано) независимое открытие той же конструкции.

Жадные геометрические остовы имеют ограниченную степень , линейное общее число ребер и общий вес, близкий к весу минимального остовного дерева Евклида . Хотя известные методы построения для них медленные, известны быстрые алгоритмы приближения с похожими свойствами. ^[4]

Жадный геометрический остов определяется из входных данных, состоящих из набора точек и параметра . Цель состоит в том, чтобы построить граф, кратчайшие расстояния которого в большинстве случаев равны геометрическим расстояниям между парами точек. Он может быть построен с помощью жадного алгоритма , который добавляет ребра по одному за раз к графу, начиная с графа без ребер с точками в качестве его вершин. Все пары точек рассматриваются в отсортированном (возрастающем) порядке по их расстояниям, начиная с ближайшей пары . Для каждой пары точек алгоритм проверяет, содержит ли построенный к настоящему моменту граф путь от до с длиной не более . Если нет, то ребро с длиной добавляется к графу. По построению результирующий граф является геометрическим остовом с коэффициентом растяжения не более . ^[3]${\displaystyle т\geq 1}$${\displaystyle т}$${\displaystyle (u,v)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle t\cdot d(u,v)}$${\displaystyle уф}$${\displaystyle d(u,v)}$${\displaystyle т}$

Наивная реализация этого метода заняла бы время на входах с точками. Это связано с тем, что рассмотрение каждой из пар точек включает в себя экземпляр алгоритма Дейкстры для поиска кратчайшего пути в графе с ребрами. Он использует пространство для хранения отсортированного списка пар точек. Более тщательные алгоритмы могут построить тот же граф за время , ^[5] или в пространстве . ^[6] Конструкция для варианта жадного остова, который использует кластеризацию графа для быстрой аппроксимации расстояний графа, выполняется со временем в евклидовых пространствах любой ограниченной размерности и может создавать остовы с (приблизительно) теми же свойствами, что и жадные остовы. ^{[7] [8]} Тот же метод можно распространить на пространства с ограниченной размерностью удвоения . ^[4]${\displaystyle O(n^{3}\log n)}$${\displaystyle n}$${\displaystyle O(n^{2})}$${\displaystyle O(n)}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{2}\log n)}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$

Та же жадная конструкция производит остовы в произвольных метрических пространствах , но в евклидовых пространствах она обладает хорошими свойствами, некоторые из которых не выполняются в более общем случае. ^[4]

Жадный геометрический остов в любом метрическом пространстве всегда содержит минимальное остовное дерево своего ввода, потому что жадный алгоритм построения следует тому же порядку вставки ребер, что и алгоритм Крускала для минимальных остовных деревьев. Если жадный алгоритм остова и алгоритм Крускала запускаются параллельно, рассматривая те же пары вершин в том же порядке, каждое ребро, добавленное алгоритмом Крускала, также будет добавлено жадным алгоритмом остова, потому что конечные точки ребра еще не будут соединены путем. В предельном случае, когда достаточно велико (например , где — число вершин в графе), два алгоритма выдают одинаковый вывод. ^[3]${\displaystyle т}$${\displaystyle т>н}$${\displaystyle n}$

В евклидовых пространствах ограниченной размерности для любой константы жадные геометрические -остовы на множествах точек имеют ограниченную степень , что подразумевает, что они также имеют ребра. ^{[9] [10] [7]} Это свойство не распространяется даже на хорошо ведущие себя метрические пространства: существуют пространства с ограниченной удвоенной размерностью , где жадный -остовы имеет неограниченную степень вершины. ^{[4] [11] [12]} Однако в таких пространствах число ребер по-прежнему равно . ^[4]${\displaystyle т}$${\displaystyle т}$${\displaystyle n}$${\displaystyle O(n)}$${\displaystyle O(n)}$

Жадные геометрические остовные элементы в евклидовых пространствах ограниченной размерности также имеют общий вес, не превышающий константу, умноженную на общий вес евклидова минимального остовного дерева . ^{[9] [10] [7]} Это свойство остается верным в пространствах ограниченной удвоенной размерности. ^[4]