Kinetyczna najbliższa para
kinetycznej najbliższej pary to kinetyczna struktura danych , która utrzymuje najbliższą parę punktów , biorąc pod uwagę zbiór P n punktów, które poruszają się w sposób ciągły w czasie w przestrzeni metrycznej. Chociaż w przypadku statycznym znanych było wiele wydajnych algorytmów, okazały się one trudne do kinetyzowania , więc opracowano nowe algorytmy statyczne, aby rozwiązać ten problem.
obudowa 2D
Podejście 1
Najprostszym kinetycznym podejściem do utrzymania najbliższej pary jest użycie wariantów triangulacji Delaunaya .
Rozważ sześciokąt i podziel go na sześć trójkątów równobocznych , a następnie utwórz triangulację Delaunaya na podstawie każdego trójkąta równobocznego, ponieważ każdy z nich jest wypukły. Suma tych sześciu triangulacji Delaunaya, tzw. równoboczny graf Delaunaya (EDG), jest supergrafem dla grafu najbliższego sąsiada (NNG); punkty końcowe krawędzi o minimalnej długości w EDG dają najbliższą parę. Łatwo jest utrzymać triangulacje Delaunaya oparte na wypukłych kształtach. Biorąc pod uwagę EDG w czasie, tworząc kinetyczne drzewo turniejowe na krawędziach EDG, można łatwo utrzymać najbliższą parę.
Ta najbliższa para KDS jest wydajna, amortyzowana, responsywna i kompaktowa, ale generalnie nie jest lokalna. Poniższe podejście przedstawia lokalny KDS dla utrzymania najbliższej pary.
Podejście 2
Drugie podejście kinetyczne opiera się na następujących obserwacjach.
Dziel i rządź
Jeśli przestrzeń wokół punktu p jest podzielona kątowo na sześć „klinów”, każdy o szerokości 60 ° , punkt najbliższy p jest najbliższym z najbliższych punktów w każdym z klinów. W dalszej części tego artykułu skupimy się na „głównych” klinach (przepołowionych przez oś x), a symetryczne argumenty zostaną zastosowane do pozostałych klinów po obróceniu płaszczyzny o ±60 ° .
Dopasowane punkty
punkty p i q są „dopasowane”, jeśli są najbliżej siebie. Oczywiście najbliższa para punktów to dopasowana para.
Rozważmy punkty p i q , takie, że p znajduje się na lewo od q i q leży w klinie wyśrodkowanym w punkcie p opisanym powyżej. Jeśli p jest punktem najbliższym q , to q musi być punktem (w tym klinie) najbliższym p , w kierunku x. Zatem zbiór par najbliższych punktów (w obrębie tego klina) w kierunku x jest nadzbiorem zbioru par najbliższych punktów.
Budowa
- Odwzoruj każdy punkt p =( x , y ) w zbiorze P na nowy punkt p' = ( u , v ) = ( x + √ 3 y , y - √ 3 x ) , tworząc zbiór P' przekształconych punktów. Zauważ, że dla punktu p punkty w „głównych” klinach mają współrzędne u i v większe lub mniejsze niż p' w tym nowym układzie współrzędnych.
- Posortuj punkty według współrzędnych x , u i v i zapisz je na listach posortowanych kinetycznie .
- Skonstruuj dwuwymiarowe drzewo zasięgu T na punktach w P' . Dla każdego węzła w w drzewie podstawowym niech T ( w ) będzie drzewem drugorzędnym powiązanym z w . To drzewo zakresu zostanie użyte do identyfikacji punktów w „głównym” klinie dla punktu w .
- Dla każdego węzła w w drzewie podstawowym i każdego węzła e w T ( w ), oblicz parę π ( w , e ) = ( b , r ), gdzie b (lub r ) jest zdefiniowany jako punkt z maksimum ( lub minimalna) współrzędna x w lewym (lub prawym) poddrzewie e . Niech Π(0) będzie zbiorem π ( w , e ) dla wszystkich par w , e w T. _ Jest to nadzbiór zbioru par najbliższych punktów (w obrębie głównego klina).
- Zbuduj kinetyczną kolejkę priorytetów na parach w Π(0) , z priorytetami określonymi przez odległość (mierzoną w oryginalnym układzie współrzędnych) między punktami w parze.
- Powtórz powyższe kroki dla płaszczyzny obróconej o ±60° , aby otrzymać kinetyczne kolejki pierwszeństwa odpowiednio na Π(1) i Π(-1) .
Najbliższa para punktów w P odpowiada minimum z minimów uzyskanych z trzech kolejek priorytetowych Π powyżej.
Konserwacja
Awarie certyfikatów mogą wystąpić w kolejkach priorytetowych i na listach posortowanych. Zamiany w kolejności punktów spowodują zmiany w T (które zajmą czas O (log 2 n ) ) i mogą spowodować wstawienia/usunięcia w kolejkach priorytetowych.
Należy zauważyć, że liczba zmian w zbiorach Π , jak zdefiniowano powyżej, nie musi być liczbą stałą. Jednak każda para, która zaczyna lub przestaje być dopasowywana w wyniku uporządkowania zmiany p i q, musi zawierać p i/lub q, a zatem istnieje tylko stała liczba dopasowanych par, które należy wstawić/usunąć z priorytetu kolejki. Można aktualizować tylko te dopasowane pary, ponieważ z definicji tylko dopasowane pary mają szansę być najbliższą parą.
Analiza
Ten KDS to:
- Responsive : zajmuje O (log 2 n ) czasu, aby przetworzyć zdarzenie
- Lokalny : ponieważ każdy punkt jest obecny w stałej liczbie kinetycznie posortowanych list i kinetycznych kolejek priorytetowych, lokalność wynika z lokalności tych struktur
- Zwartość : zwartość wynika ze zwartości kinetycznie posortowanych list i kinetycznych kolejek priorytetowych
- Efektywne : każda zamiana na posortowanych listach powoduje stałą liczbę wstawień i usunięć w kinetycznych kolejkach priorytetów. Zakładając, że ruch punktów jest pseudoalgebraiczny, istnieje wielomianowa liczba zamian, a zatem wielomianowa liczba zdarzeń jest przetwarzana przez ten KDS, dzięki czemu jest wydajny
Podejście to można wykorzystać do utrzymania najbliższej pary w wyższych wymiarach.