Custos de execução aprox. pesquisa de vizinho mais próximo em um salto de quadtree

NOTA : A pergunta foi reafirmada em minhas respostas: Supondo que agora possamos encontrar os ancestrais de irmãos mais baixos no tempo , a RNA pode realmente ser executada em O ( log n ) ?$O(1)$$O(\log n)$

Quadtrees são índices espaciais eficientes. Eu tenho um quebra-cabeça com a implementação de uma pesquisa de vizinhos mais próximos em uma estrutura de quadtree compactada, conforme descrito em [2]. (Sem entrar em detalhes, a pesquisa vai de cima para baixo ao longo dos chamados quadrados equidistantes, terminando no nó da cauda de um caminho equidistante. Na imagem anexada, pode ser que um dos nós no sudeste esteja cheio de pontos.)

Para que o algoritmo funcione, é necessário manter para cada nó - um quadrado com pelo menos dois quadrantes não vazios - ponteiros para cada nó ancestral mais baixo (o mais próximo da hierarquia) em cada uma das quatro direções (norte, oeste, sul , leste). Eles são indicados pelas setas verdes do ancestral oeste dos nós (a seta aponta para o centro do quadrado ancestral).

O documento afirma que esses ponteiros podem ser atualizados em O (1) durante inserções e exclusões de pontos. No entanto, ao olhar para a inserção do ponto verde, parece que preciso atualizar qualquer número arbitrário de ponteiros, neste caso seis deles.

Espero um truque para fazer essa atualização do ponteiro em tempo constante. Talvez exista uma forma de indireção que possa ser explorada?

EDITAR:

A secção relevante do papel é de 6,3, onde se lê: "se o caminho tem curvas, em seguida, para além da mais baixas antepassados de q , devemos considerar também para cada um dos 2 d instrues ancestral mais baixo de q que vai nessa direção [...] A localização desses quadrados a partir de q pode ser feita em O ( 1 ) tempo por quadrado se associarmos ponteiros adicionais de 2 d a cada quadrado em Q $log(c/ε)$$q$$2^d$$q$$q$$O(1)$$2^d$$Q_0$apontando para seus antepassados ​​mais próximos para cada direção. Esses ponteiros também podem ser atualizados no tempo durante uma inserção ou exclusão de um ponto ".$O(1)$

[2]: Eppstein, D. e Goodrich, MT e Sun, JZ, “The Skip Quadtree: Uma estrutura dinâmica simples de dados para dados multidimensionais”, em Anais do vigésimo primeiro simpósio anual em geometria computacional, pp. 296-305 2005.

Como Davi, não sei por que Jonathan fez essa observação sobre os indicadores. Eles não são necessários. Como David mencionou acima, a propriedade essencial é que, quando estamos localizando um ponto em uma folha v em Q_0, é suficiente lembrar os nós irmãos (e suas caixas) no quadtree pular. Quando processamos uma caixa a partir de P, fazemos um local de ponto para a caixa de folha mais próxima ao nosso ponto de consulta, inserindo as caixas de irmãos à medida que descemos. Parece que isso seria mais ou menos o mesmo que sua resposta. Além disso, esse procedimento é muito semelhante, por exemplo, à forma como a localização aproximada dos pontos é feita no seguinte artigo: Arya, Sunil e Mount, David M. e Netanyahu, Nathan S. e Silverman, Ruth e Wu, Angela Y., "Um algoritmo ideal para o vizinho mais próximo aproximado pesquisando dimensões fixas", JACM, 1998. De fato,

Pode-se pensar em pular quadtree como uma implementação de lista de pulos de uma estrutura de dados que armazena os pontos de acordo com sua ordem z. É (sem dúvida) pelo menos conceitualmente mais simples ...

Veja o capítulo 2 aqui: http://goo.gl/pLiEO .

E sim, supondo que você possa executar algumas operações básicas da ordem z em tempo constante, você pode definitivamente executar a ANN em tempo logarítmico. O capítulo mencionado acima também mostra que não há como evitar operações bizarras se alguém quiser quadríceps compactados. Observe que a operação LCA não é necessária ...

Também sinto intuitivamente que alguém poderia viver sem esses ponteiros e, como preciso persistir em todos os nós para fazer o disco rígido em algum momento, qualquer redução nos ponteiros é grande.

$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$

EDIT (abril de 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)$

Portanto, a menos que esteja faltando algo crucial, o algoritmo não pode atingir a velocidade declarada. Quaisquer comentários ou idéias?