Kinetyczne euklidesowe minimalne drzewo rozpinające

Kinetyczne minimalne euklidesowe drzewo rozpinające to kinetyczna struktura danych , która utrzymuje euklidesowe minimalne drzewo rozpinające (EMST) zbioru P n punktów, które poruszają się w sposób ciągły.

Dla zbioru punktów P w przestrzeni dwuwymiarowej istnieją dwa algorytmy kinetyczne do utrzymania EMST.

Rahmati i Zarei budują kinetyczną strukturę danych w oparciu o kinetyczną triangulację Delaunaya, aby obsłużyć aktualizacje EMST w czasie polilogu na zdarzenie. Ich kinetyczna $struktura$ danych obsługuje zdarzenia, gdzie m to Delaunaya ruchomych Ich kinetyczne podejście może dobrze działać w przypadku utrzymania minimalnego drzewa rozpinającego (MST) grafu planarnego , którego wagi krawędzi zmieniają się w ciągłej funkcji czasu.

Abam, Rahmati i Zarei zapewniają znaczną poprawę dokładnego zachowania kinetyki minimalnego euklidesowego drzewa rozpinającego . Ich kinetyczna struktura danych obsługuje niemal sześcienną liczbę zdarzeń.