Por que alguém usaria um Octree sobre uma árvore KD?

Tenho alguma experiência em computação científica e usei extensivamente kd-trees para aplicativos BSP (particionamento de espaço binário). Recentemente, familiarizei-me com octrees, uma estrutura de dados semelhante para particionar espaços euclidianos em 3D, mas que funciona em intervalos regulares fixos, pelo que entendi.

Um pouco de pesquisa sobre independência parece indicar que o kd-trees geralmente tem desempenho superior para a maioria dos conjuntos de dados - mais rápido para construir e consultar. Minha pergunta é: quais são as vantagens de octrees no desempenho espacial / temporal ou não, e em quais situações elas são mais aplicáveis ​​(eu ouvi a programação de gráficos 3D)? Um resumo das vantagens e problemas de ambos os tipos me agradeceria mais.

Como um extra, se alguém pudesse elaborar sobre o uso da estrutura de dados da árvore R e suas vantagens, eu também ficaria grato por isso. As árvores R (mais do que as octrees) parecem ser aplicadas de maneira bastante semelhante às árvores kd para pesquisas de k-vizinho mais próximo ou de alcance.

As células em uma árvore podem ter uma alta proporção, enquanto as células octree têm a garantia de serem cúbicas. Como se trata de um quadro teórico, apresentarei a razão teórica para a alta proporção de aspecto ser um problema: torna impossível o uso de limites de volume para controlar o número de células que você deve examinar ao resolver consultas de vizinhos mais próximas.$kD$

Mais detalhadamente: se você solicitar um vizinho mais próximo, próximo à , a um ponto de consulta , e o vizinho mais próximo estiver na distância , você normalmente termina uma pesquisa que examina todas as células da estrutura de dados que chegam de dentro para a parte externa de um anel ou invólucro anular com raio interno e raio externo . Se as células tiverem uma proporção de aspecto limitada, como estão em uma quadtree, pode haver no máximo essas células, e você poderá provar bons limites no tempo para a consulta. Se a proporção não for limitada, como em uma árvore , esses limites não se aplicarão.q d d ( 1 + ϵ ) d 1 / ϵ d - 1 k $\epsilon$$q$$d$$d$$(1+\epsilon)d$$1/\epsilon^{d-1}$$kD$

$kD$ árvores de têm uma vantagem diferente sobre as quadrípedes, na medida em que elas garantem uma profundidade logarítmica máxima, o que também contribui para o tempo para uma consulta de vizinho mais próximo. Mas a profundidade de uma quadtree é, no máximo, o número de bits de precisão da entrada que geralmente não é grande, e existem métodos teóricos para controlar a profundidade como essencialmente logarítmica (consulte a estrutura de dados quadtree).

Eu e um grupo de amigos estamos trabalhando em um jogo RTS espacial como um projeto paralelo divertido. Estamos usando muitas das coisas que aprendemos na Ciência da Computação para torná-la altamente eficiente, o que nos permite criar exércitos maciços mais tarde.

Para esse propósito, consideramos o uso do kd-trees, mas rapidamente os descartamos: inserções e exclusões são extremamente comuns em nosso programa (considere uma nave voando pelo espaço), e essa é uma bagunça profana com o kd-trees. Por isso, escolhemos octrees para o nosso jogo.

quais são as vantagens dos octrees no desempenho espacial / temporal ou não, e em quais situações elas são mais aplicáveis ​​(eu ouvi a programação de gráficos 3D)?

As árvores kD são árvores binárias balanceadas e outras são tentativas, de modo que as vantagens e desvantagens provavelmente são herdadas dessas estruturas de dados mais gerais. Especificamente:

• O reequilíbrio pode ser caro (os octrees não precisam de reequilíbrio).
• O balanceamento lida melhor com a heterogeneidade porque é adaptável.
• Maior fator de ramificação em octrees significa árvores mais rasas (menos indiretos e alocações) para distribuições homogêneas.

Além disso, a bissecção (como em octrees) se presta a uma implementação trivial em termos de manipulação de bits. Da mesma forma, imagino que os octrees possam se beneficiar muito das distâncias pré-computadas ao fazer pesquisas de alcance.

EDITAR

Aparentemente, minhas referências a tentativas e homogeneidade precisam de esclarecimentos.

As tentativas são uma família de estruturas de dados representadas por árvores de dicionários e são usadas como dicionários para chaves que são sequências (principalmente cadeias de caracteres, mas também seqüências de DNA e os bits em um valor de hash para tentativas de hash). Se cada dicionário mapeia um bit de cada uma das coordenadas x, ye z (bit mais significativo no primeiro nível do trie, próximo bit significativo no segundo nível etc.), então o trie é uma octree que subdivide uniformemente o espaço 3D. Portanto, os octrees herdam as características das tentativas que são, em geral:

• Alto fator de ramificação pode significar árvores rasas que incorrem em poucos indiretos, portanto a pesquisa é rápida, por exemplo, 20 níveis de árvore binária podem ser armazenados em 4 níveis de uma árvore com um fator de ramificação de 256.
• As tentativas não são reequilibradas durante inserções e exclusões, economizando uma operação cara e necessária para árvores binárias balanceadas.

A desvantagem é que a heterogeneidade pode resultar em tentativas / octrees desequilibradas, portanto as pesquisas podem exigir muitos indiretos. O problema equivalente nas tentativas é resolvido usando a compactação de arestas para recolher vários níveis de indireção em um único nível. Octrees não fazem isso, mas não há nada para impedi-lo de compactar uma octree (mas acho que você não poderia chamar o resultado de octree!).

Para comparação, considere um dicionário especializado para chaves de cadeia de caracteres que é representado como um trie. O primeiro nível da série ramifica no primeiro caractere na chave. O segundo nível no segundo caractere e assim por diante. Qualquer cadeia de caracteres pode ser procurada pesquisando o primeiro caractere da chave no dicionário para obter um segundo dicionário usado para pesquisar o segundo caractere na chave e assim por diante. Um conjunto de cadeias de teclas aleatórias seria uma distribuição homogênea . Um conjunto de cadeias de teclas que compartilham algum prefixo (por exemplo, todas as palavras que começam com "anti") são heterogêneasdistribuição. No último caso, o primeiro dicionário contém apenas uma ligação, para "a", o segundo único para "n" e assim por diante. A busca por qualquer mapeamento na série está sempre pesquisando os mesmos quatro dicionários com as mesmas quatro chaves. Isso é ineficiente e é o que os octrees fazem se, por exemplo, forem usados ​​para armazenar distribuições heterogêneas de partículas, onde a grande maioria das partículas se encontra em um pequeno volume dentro do espaço vetorial.

Octrees são úteis como um tipo de dados base para modelos de continuum, veja, por exemplo, o solucionador de fluxo Gerris . A vida é bastante difícil na dinâmica de fluidos, portanto, saber que os tamanhos de todos os seus subcubos depende apenas da profundidade deles deve ser um fator simplificador.

Advertência: Eu não sou um dinamista fluido!