Uma maneira eficaz de representar quadtrees

Uma quadtree pode ser representada sem ponteiros, codificando cada nó preto com um inteiro quaternário cujos dígitos refletem subdivisões quadrantes sucessivas. Referimo-nos ao array ordenado de nós pretos como “quadtree linear” e mostramos que isso introduz uma economia de pelo menos 66 por cento do espaço de armazenamento do computador requerido por quadtrees regulares. Alguns algoritmos utilizando quadtrees lineares são apresentados, a saber, (i) codificando um pixel de um array 2 n × 2 >n (ou tela) em seu código quaternário; (ii) encontrando nós adjacentes; (iii) determinando a cor de um nó; (iv) sobrepondo duas imagens. É demonstrado que os algoritmos (i)-(iii) podem ser executados em tempo logarítmico, enquanto a superposição pode ser realizada em tempo linear em relação ao número total de nós pretos. O artigo também mostra que a capacidade dinâmica de uma quadtree pode ser efetivamente simulada.