Прямоугольное наименьшее остовное дерево

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

Прямоугольное наименьшее остовное дерево (англ. Rectilinear Minimum Spanning Tree, RMST) набора из n точек на плоскости (в более общем случае — в пространстве $\mathbb {R} ^{d}$) — это минимальное остовное дерево этого набора, где веса рёбер между каждой парой точек равны расстоянию городских кварталов между этими двумя точками.

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

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

Планарный случай

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

Результирующий граф имеет лишь линейное число рёбер и может быть построен за время O(n log n), используя алгоритм «разделяй и властвуй» или алгоритм заметающей прямой.

Приложения

Проектирование электроники

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

См. также

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