Prostoliniowe minimalne drzewo rozpinające
W teorii grafów prostoliniowe minimalne drzewo rozpinające ( RMST ) zbioru n punktów na płaszczyźnie (lub bardziej ogólnie w ℝ d ) jest minimalnym drzewem rozpinającym tego zbioru, w którym waga krawędzi między każdą parą punktów jest prostoliniową odległością między tymi dwoma punktami.
Właściwości i algorytmy
Jawnie konstruując pełny graf na n wierzchołkach, który ma n ( n -1)/2 krawędzi, można znaleźć prostoliniowe minimalne drzewo rozpinające przy użyciu istniejących algorytmów znajdowania minimalnego drzewa rozpinającego. W szczególności użycie algorytmu Prima z macierzą sąsiedztwa daje złożoność czasową O( n 2 ).
Planarny przypadek
W przypadku planarnym istnieją bardziej wydajne algorytmy. Opierają się na założeniu, że połączenia mogą zachodzić tylko z najbliższym sąsiadem punktu w każdej oktancie - to znaczy z każdym z ośmiu obszarów płaszczyzny wyznaczonych przez oś współrzędnych z tego punktu i ich dwusiecznych.
Otrzymany graf ma tylko liniową liczbę krawędzi i można go skonstruować w O ( n log n ) przy użyciu algorytmu dziel i zwyciężaj lub algorytmu zamiatania linii .
Aplikacje
Projekt elektroniczny
Problem często pojawia się przy fizycznym projektowaniu obwodów elektronicznych . W nowoczesnych układach scalonych o dużej gęstości prowadzenie przewodów odbywa się za pomocą przewodów składających się z segmentów biegnących poziomo w jednej warstwie metalu i pionowo w drugiej warstwie metalu. W rezultacie długość drutu między dwoma punktami jest naturalnie mierzona odległością prostoliniową. Chociaż trasowanie całej sieci z wieloma węzłami jest lepiej reprezentowane przez prostoliniowe drzewo Steinera , RMST zapewnia rozsądne przybliżenie i oszacowanie długości drutu.