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