Прямоугольное наименьшее остовное дерево
Прямоугольное наименьшее остовное дерево (Шаблон:Lang-en, RMST) набора из n точек на плоскости (в более общем случае — в пространстве ) — это минимальное остовное дерево этого набора, где веса рёбер между каждой парой точек равны расстоянию городских кварталов между этими двумя точками.
Свойства и алгоритмы
Путём построения полного графа на n вершинах, который имеет n(n-1)/2 рёбер, прямоугольное наименьшее остовное дерево может быть найдено с помощью существующих алгоритмов для нахождения минимального остовного дерева. В частности, использование алгоритм Прима для матрицы смежности даёт сложность O(n2).
Планарный случай
В планарном случае существуют более эффективные алгоритмы. Они основаны на идее, что соединение может только быть с ближайшим соседом точки в каждом октанте, то есть в восьми областях плоскости, образованных координатными осями и биссектрисами.
Результирующий граф имеет лишь линейное число рёбер и может быть построен за время O(n log n), используя алгоритм «разделяй и властвуй»Шаблон:Sfn или алгоритм заметающей прямойШаблон:Sfn.
Приложения
Проектирование электроники
Задача обычно возникает при Шаблон:Не переведено 5 электронных схем. В современных интегральных схемах высокой плотности трассировка осуществляется проводниками, которые состоят из горизонтальных отрезков в одном слое и вертикально в другом слое. В результате длина проводника между двумя точками естественно измерять прямоугольным расстоянием. Хотя трассировка всей сети лучше представлена Шаблон:Не переведено 5, RMST обеспечивает приемлемое приближение и оценку длины проводниковШаблон:Sfn.