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

В теории графов — прямолинейное минимальное остовное дерево ( RMST ) набора из n точек на плоскости (или, в более общем смысле, в $\mathbb {R} ^{d}$ ) — минимальное остовное дерево этого набора, где вес ребра между каждой парой точек — это прямолинейное расстояние между этими двумя точками.

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

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

Плоский случай

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

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

Приложения

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

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

См. также

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

Ссылки

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

[1] LJ Guibas и J. Stolfi, «О вычислении всех ближайших северо-восточных соседей в метрике L1», Information Processing Letters, 17 (1983), стр. 219–223.

[2] Хай Чжоу, Нарендра Шеной, Уильям Николлс, «Эффективное построение минимального остовного дерева без триангуляции Делоне», Information Processing Letters 81 (2002) 271–276

[3] ФК Хван. «О минимальных деревьях Штейнера с прямолинейным расстоянием». SIAM Journal по прикладной математике , 30:104–114, 1976.

[1]

[2]

[3]