Actas de congresos
Vectorized algorithms for quadtree construction and descent
Fecha
2012-10-01Registro en:
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.
0302-9743
1611-3349
10.1007/978-3-642-33078-0_6
2-s2.0-84866681228
Autor
Universidade Estadual Paulista (Unesp)
Institución
Resumen
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.