Koszty wykonania ok. szukaj najbliższego sąsiada w pomijanym quadtree

UWAGA : Pytanie zostało ponownie sformułowane w moich odpowiedziach: Zakładając, że możemy znaleźć najniższych przodków rodzeństwa w czasie , czy ANN można naprawdę wykonać w ?$O(1)$$O(\log n)$

Czworoboki są wydajnymi wskaźnikami przestrzennymi. Mam łamigłówkę z implementacją wyszukiwania najbliższego sąsiada w skompresowanej strukturze quadtree, jak opisano w [2]. (Bez wchodzenia w szczegóły, wyszukiwanie odbywa się od góry do dołu wzdłuż tak zwanych równoodległych kwadratów, kończąc się na węźle ogonowym jednakowo odległej ścieżki. Na załączonym obrazie może to być dowolny z węzłów na południowym wschodzie wypełnionych punktami.)

Aby ich algorytm działał, należy zachować dla każdego węzła - kwadrat z co najmniej dwoma niepustymi kwadrantami - wskaźniki dla każdego najniższego (najbliższego w hierarchii) węzła przodka w każdym z czterech kierunków (północ, zachód, południe , wschód). Wskazują na to zielone strzałki dla zachodniego przodka węzłów (strzałka wskazuje środek kwadratu przodka).

Artykuł twierdzi, że wskaźniki te można aktualizować w O (1) podczas wstawiania i usuwania punktów. Jednak patrząc na wstawienie zielonego punktu, wydaje się, że muszę zaktualizować dowolną liczbę wskaźników, w tym przypadku sześć.

Mam nadzieję, że uda mi się zrobić aktualizację wskaźnika w stałym czasie. Może istnieje jakaś forma pośrednictwa, którą można wykorzystać?

EDYTOWAĆ:

Odpowiednia część artykułu to 6.3, gdzie brzmi: „jeśli ścieżka ma zakręty, to oprócz najniższych przodków , powinniśmy również rozważyć dla każdego z kierunków najniższy przodek który zmierza w tym kierunku [...] Znalezienie tych kwadratów z można wykonać w czasie na kwadrat, jeśli skojarzymy dodatkowe wskaźników z każdym kwadratem w wskazując jego najbliższych przodków dla każdego kierunku Wskaźniki te można również aktualizować w czasie podczas wstawiania lub usuwania punktu. ”$log(c/ε)$$q$$2^d$$q$$q$$O(1)$$2^d$$Q_0$$O(1)$

[2]: Eppstein, D. i Goodrich, MT i Sun, JZ, „The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional Data”, w toku dwudziestego pierwszego dorocznego sympozjum na temat geometrii obliczeniowej, s. 296–305 , 2005.

Podobnie jak David, nie wiem, dlaczego Jonathan umieścił tę uwagę na temat 2 wskaźników. Nie są potrzebne. Jak wspomniano powyżej David, podstawową właściwością jest to, że kiedy robimy lokalizację punktu do liścia v w Q_0, wystarczy zapamiętać węzły rodzeństwa (i ich pola) w poczwórnym drzewie pomijanym. Kiedy przetwarzamy pudełko z P, robimy lokalizację punktu dla pudełka z liśćmi najbliższego naszemu punktowi zapytania, wstawiając pudełka rodzeństwa, gdy schodzimy w dół. Wygląda na to, że to mniej więcej to samo, co twoja odpowiedź. Ponadto procedura ta jest bardzo podobna, na przykład w odniesieniu do przybliżonej lokalizacji punktu w poniższej pracy: Arya, Sunil and Mount, David M. i Netanyahu, Nathan S. i Silverman, Ruth i Wu, Angela Y., „Optymalny algorytm do wyszukiwania przybliżonych wymiarów najbliższego sąsiada”, JACM, 1998. Rzeczywiście,

Można pomyśleć o pominięciu kwadratu jako implementacji listy pominięć struktury danych przechowującej punkty zgodnie z ich kolejnością. Jest (prawdopodobnie) co najmniej koncepcyjnie prostsze ...

Zobacz rozdział 2 tutaj: http://goo.gl/pLiEO .

I tak, zakładając, że możesz wykonać kilka podstawowych operacji rzędu Z w stałym czasie, zdecydowanie możesz wykonać ANN w czasie logarytmicznym. Powyższy rozdział pokazuje również, że nie można uniknąć dziwnych operacji, jeśli chce się skompresowanych czterech drzew. Uwaga: operacja LCA nie jest konieczna ...

Intuicyjnie też czuję, że można żyć bez tych wskaźników, a ponieważ muszę w pewnym momencie utrzymać wszystkie węzły na dysku twardym, wszelkie redukcje wskaźników są świetne.

$l_{best}$$r_{max}$${dist}'(v,q)$$q$$v$$v$

$P$$l_{best}$$p_0$$Q_0$$r_{max}$$l_{best}$$\infty$$p_0$$Q_0$$q$$l_{best}$$r_{max}$$q$${dist}'(q,v)$${dist}(q,v)$$v$$q$$q$$v$

${dist}(q,v) > r_{max}$$q$$\geq 2$$P$

$q$$p_0$$Q_j$$r_{max}$$Q_{j-1}$$Q_0$

$r_{max}$$P$

EDYCJA (kwiecień 2013)

$r_{max}$

$O(\sqrt n)$

$O(\epsilon^{1−d}(\log n+\log \epsilon^{−1}))$

$\epsilon = 1$$v$

$Q_0$

$O(\sqrt n)$$d = 2$$\epsilon = 1$$O(\log n)$

Tak więc, chyba że brakuje mi czegoś istotnego, algorytm nie może osiągnąć określonej prędkości. Wszelkie komentarze lub pomysły?