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

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

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

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

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

Планарный случайПравить

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

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

ПриложенияПравить

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

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

См. такжеПравить

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

ПримечанияПравить

↑ Guibas, Stolfi, 1983, с. 219-223.
↑ Zhou, Shenoy, Nicholls, 2002, с. 271–276.
↑ Hwang, 1976, с. 104–114.

ЛитератураПравить

Guibas L.J., Stolfi J. On computing all northeast nearest neighbors in the L1 metric // Information Processing Letters. — 1983. — Вып. 17.
Hai Zhou, Narendra Shenoy, William Nicholls. Efficient minimum imgning tree construction without Delaunay triangulation // Information Processing Letters. — 2002. — Вып. 81.
Hwang F. K. On Steiner minimal trees with rectilinear distance // SIAM Journal on Applied Mathematics. — 1976. — Вып. 30.

[_87a58a97e8b02d0e-1] Guibas, Stolfi, 1983, с. 219-223.

[_94c97749f89cdd19-2] Zhou, Shenoy, Nicholls, 2002, с. 271–276.

[_705f0ddfef4e9d57-3] Hwang, 1976, с. 104–114.

[1]

[2]

[3]