Прямолинейное минимальное остовное дерево - Rectilinear minimum spanning tree

Пример прямолинейного минимального остовного дерева из случайных точек.

В теория графов, то прямолинейное минимальное остовное дерево (RMST) набора п точки в самолет (или, в более общем смысле, в ℝd) это минимальное остовное дерево этого набора, где вес ребра между каждой парой точек равен прямолинейное расстояние между этими двумя точками.

Свойства и алгоритмы

Путем явного построения полный график на п вершины, которые имеют п(п-1) / 2 ребра, прямолинейное минимальное остовное дерево может быть найдено с использованием существующих алгоритмов поиска минимального остовного дерева. В частности, используя Алгоритм Прима с матрица смежности дает временную сложность O (п2).

Планарный корпус

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

Полученный граф имеет только линейное количество ребер и может быть построен за O (п журнал п) с помощью разделяй и властвуй алгоритм[1] или алгоритм линии развертки.[2]

Приложения

Электронный дизайн

Проблема обычно возникает в физический дизайн из электронные схемы. В современных высокоплотных интегральные схемы провод маршрутизация выполняется проволокой, которая состоит из сегментов, идущих горизонтально в одном слое металла и вертикально в другом слое металла. В результате длина провода между двумя точками, естественно, измеряется с прямолинейным расстоянием. Хотя маршрутизация всей сети с несколькими узлами лучше представлена прямолинейное дерево Штейнера, RMST обеспечивает разумное приближение и оценку длины провода.[3]

Смотрите также

использованная литература

  1. ^ L.J. Guibas и J. Stolfi, "О вычислении всех ближайших северо-восточных соседей в метрике L1", Information Processing Letters, 17 (1983), стр. 219-223
  2. ^ Хай Чжоу, Нарендра Шеной, Уильям Николлс, «Эффективное построение минимального остовного дерева без триангуляции Делоне», Информационные письма 81 (2002) 271–276
  3. ^ Ф. К. Хван. «О минимальных деревьях Штейнера с прямолинейным расстоянием». Журнал SIAM по прикладной математике, 30:104–114, 1976.