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

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

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

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

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

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

Приложения

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

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

См. также

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

Примечания

Литература

Для улучшения этой статьи желательно : Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.