3.1 Algorytmy oparte na metodzie logarytmicznej
Pierwsze algorytmy oparte są na zastosowaniu metody logarytmicznej Bentleya . Zastosowanie to pojawiło się po raz pierwszy w pracy Smid . (Zobacz też Schwarz .)
Niech S będzie bieżącym zbiorem punktów w ℝD, a n niech oznacza jego rozmiar. Zapisz n w systemie liczb binarnych, n=∑i≥0ai2i, gdzie ai ∈ {0,1}. Podzielmy S (arbitralnie) na podzbiory: dla każdego i takiego, że ai = 1 istnieje jeden podzbiór Si, o rozmiarze 2i. Ponadto, dla każdego takiego i, istnieje liczba rzeczywista δi taka, że d(S) ≤ δi ≤ d (Si) Struktura danych składa się z następujących elementów.
(1)
Najbliższa para S i jej odległość δ
(2)
Dla każdego i takiego, że ai = 1, δi -siatka przechowująca punkty Si. Zakładamy, że niepuste komórki tej siatki są przechowywane w zrównoważonym drzewie wyszukiwania binarnego, posortowane leksykograficznie według ich „lewych dolnych” rogów.
Teraz rozważmy wstawienie nowego punktu p. Dla każdego i takiego, że ai = 1, znajdujemy komórkę δi-siatki, która zawiera p wraz z 3D – 1 sąsiednimi komórkami. Następnie obliczamy odległości pomiędzy p i wszystkimi punktami Si, które są zawarte w tych komórkach. Jeśli znajdziemy odległość mniejszą niż δ, to aktualizujemy δ, oraz najbliższą parę. Pozostaje zaktualizować resztę struktury danych. Niech j będzie indeksem takim, że a0 = a1 = … = aj – 1 i aj = 0. Niech Sj := {p} ∪ S0 ∪ S1 ∪ … ∪ Sj – 1 oraz δj := δ. Budujemy siatkę δj dla zbioru Sj, i odrzucamy siatki dla zbiorów S0, S1,… Sj – 1 (tym samym czyniąc te zbiory pustymi).
Aby udowodnić poprawność tego algorytmu, zauważmy, że ponieważ d(S) ≤ δi, wystarczy porównać p ze wszystkimi punktami Si, które są w sąsiedztwie p – w siatce δi. Stąd, najbliższa para jest aktualizowana poprawnie. Ponadto, nowa wartość Sj spełnia d(S ∪ {p}) ≤ δj ≤ d(Sj), a dla wszystkich i > j, mamy d(S ∪ {p} ≤ δi d(Si). Wreszcie, zaktualizowana struktura danych zawiera siatkę przechowującą 2i punktów dla każdego i takich, że binarna reprezentacja n + 1 zawiera jedynkę na pozycji i.
Analizujemy złożoność algorytmu wstawiania. Najpierw zauważmy, że skoro δi ≤ d(Si), to sąsiedztwo p w siatce δi zawiera co najwyżej stałą liczbę punktów Si. Stąd, na każdą siatkę poświęcamy O(log n) czasu. Ponieważ struktura danych zawiera logarytmiczną liczbę kratek, pierwsza część algorytmu wstawiania zajmuje O(log 2n) czasu.
Rozważmy drugą część algorytmu, w której budujemy δj -siatkę. Ten krok zajmuje O(|Sj |log |Sj|) czasu, ze względu na sortowanie. Jeśli jednak będziemy przechowywać punkty w odpowiedniej kolejności, to siatkę można zbudować w czasie O(|Sj|) = O(2j). (Zobacz szczegóły.) Ponieważ j może przyjąć dowolną wartość pomiędzy zerem a ⌊log n⌋, czas wstawiania ulega dużym wahaniom. Twierdzimy jednak, że czas amortyzacji dla drugiego kroku jest ograniczony przez O(log n).
Aby udowodnić to twierdzenie, załóżmy, że zaczynamy od pustego zbioru S i wykonujemy sekwencję n wstawień. Niech kj będzie liczbą przypadków, w których podczas tych wstawień budujemy siatkę dla podzbioru o rozmiarze 2j Wtedy kj jest co najwyżej równe liczbie liczb całkowitych składających się z co najwyżej 1 + ⌊log n⌋ bitów, których j najmniej znaczących bitów jest równych jeden, i których (j + 1)-szy bit jest równy zero. Czyli mamy
Całkowity czas poświęcony na drugi krok podczas n wstawień jest ograniczony przez
co dowodzi twierdzenia.
Wykazaliśmy, że czas działania całego algorytmu utrzymywania najbliższej pary jest ograniczony przez O(log 2n) czas najgorszego przypadku plus O(log n) amortyzowany czas na wstawienie. Używając standardowych technik (patrz Overmars ), możemy przekształcić strukturę danych w taki sposób, że drugi krok zajmuje czas logarytmiczny w najgorszym przypadku. Mamy więc strukturę danych, która przechowuje najbliższą parę w O(log 2n) najgorszym przypadku czasu na wstawienie. Struktura ta ma rozmiar O(n).
Zauważ, że pierwszy krok algorytmu zajmuje O(log 2n) czasu, podczas gdy drugi krok zajmuje tylko O(log n) czasu. Sugeruje to, że możliwe jest jego ulepszenie. W istocie, zamiast zapisywać n w binarnym systemie liczbowym, używamy systemu liczbowego o podstawie log n. (Patrz Overmars lub Schwarz .) W ten sposób oba kroki zajmują O(log 2n/log log n) czasu, podczas gdy używana przestrzeń pozostaje liniowa.
Stąd mamy strukturę danych o liniowym rozmiarze, która utrzymuje najbliższą parę w O(log2 n /log log n) najgorszym przypadku czasu na wstawienie. Zauważmy, że algorytm używa funkcji podłogi w celu znalezienia komórki siatki zawierającej nowy punkt p. Poprzez zastąpienie siatki zdegradowaną siatką, algorytm może być zaimplementowany w algebraicznym modelu drzewa obliczeniowego.
Wciąż możliwe jest ulepszenie powyższej struktury danych. Rozważmy ponownie strukturę danych opartą na reprezentacji n w binarnym systemie liczbowym. Główna obserwacja jest następująca: Jeśli wstawimy punkt p, to dla każdego i takiego, że ai = 1, znajdujemy komórkę δi -girda, która zawiera p (plus komórki sąsiednie). Czyli, wykonujemy zapytania o położenie punktów w logarytmicznej liczbie kratek, ale zawsze z tym samym punktem zapytania p. W Schwarz i Smid , pokazano, że technika kaskadowania frakcji może być rozszerzona tak, że wszystkie te zapytania razem mogą być rozwiązane w czasie O(log n log n). Główny problem polega na tym, że mamy siatki o różnych rozmiarach. Dlatego należy wprowadzić porządek na komórkach siatki, który jest „kompatybilny” z wszystkimi tymi rozmiarami. W takim uporządkowaniu jest to zdefiniowane. W rezultacie, zlokalizowanie punktu p we wszystkich siatkach wymaga O(log n) porównań. Ponieważ jednak uporządkowanie jest dość skomplikowane, każde porównanie zajmuje O(log log n) czasu. Ogólnie rzecz biorąc, otrzymujemy strukturę danych o rozmiarze O(n), która utrzymuje najbliższą parę w czasie O(log n log n) amortyzowanym na każde wstawienie. Zauważ, że potrzebujemy funkcji podłogi do tego wyniku. Prawdopodobnie można to zrobić w najgorszym przypadku, ale szczegóły będą żmudne. Nie jest jasne, czy porządek na komórkach siatki może być również zdefiniowany, jeśli używamy zdegradowanych siatek zamiast standardowych siatek.
Na koniec wspominamy o rozszerzeniu powyższej struktury danych. Opisana powyżej struktura mocno wykorzystuje fakt, że wstawiamy tylko punkty. Okazuje się jednak, że struktura ta może być przystosowana do radzenia sobie z aktualizacjami semi-online, zdefiniowanymi przez Dobkina i Suri . Sekwencja aktualizacji jest nazywana semi-online, jeśli wstawienia są on-line – tzn. przychodzą w nieznanej kolejności – ale kiedy punkt jest wstawiany, wiemy po ilu aktualizacjach od momentu wstawienia zostanie on usunięty. Ta dodatkowa informacja o usunięciach może być użyta do zagwarantowania, że kiedy punkt jest usuwany, zawsze jest zawarty w siatce przechowującej mały podzbiór. Ponieważ podczas usuwania minimalna odległość może wzrosnąć, przechowujemy dodatkowe informacje w strukturze danych w celu efektywnego uaktualnienia najbliższej pary. W ten sposób otrzymujemy strukturę danych o rozmiarze O(n), która utrzymuje najbliższą parę w czasie O(log 2n) najgorszego przypadku na aktualizację semi-online. Po szczegóły odsyłamy czytelnika do Dobkina i Suri oraz Smida .