Vectorized algorithms for quadtree construction and descent
Nenhuma Miniatura disponível
Data
2012-10-01
Autores
Marinho, Eraldo P. [UNESP]
Baldassin, Alexandro [UNESP]
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
This paper presents vectorized methods of construction and descent of quadtrees that can be easily adapted to message passing parallel computing. A time complexity analysis for the present approach is also discussed. The proposed method of tree construction requires a hash table to index nodes of a linear quadtree in the breadth-first order. The hash is performed in two steps: an internal hash to index child nodes and an external hash to index nodes in the same level (depth). The quadtree descent is performed by considering each level as a vector segment of a linear quadtree, so that nodes of the same level can be processed concurrently. © 2012 Springer-Verlag.
Descrição
Palavras-chave
Breadth-first, Child node, Hash table, Index nodes, Linear quadtree, Quad trees, Time complexity, Tree construction, Parallel architectures, Algorithms
Como citar
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), v. 7439 LNCS, n. PART 1, p. 69-82, 2012.