Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding
W. Safwan, Ameur A. · International Journal of Computer Applications · 2015
This paper presents a new quadtree structure: Cardinal Neighbor Quadtrees (CN-Quadtree), that allows finding neighbor quadrants in constant time regardless of their sizes.Gunter Schrack's solution [1] was able to compute the location code of equal size neighbors in constant-time without guaranteeing their existence.The structure proposed by Aizawa [3][2][3]was able to determine the existence of equal or greater size neighbors and compute their location in constant time, to which the access-time complexity should be added.The proposed structure, the Cardinal Neighbor Quadtree, a pointer based data structure, can determine the existence, and access a smaller, equal or greater size neighbor in constant-time O(1).The time complexity reduction is obtained through the addition of only four pointers per leaf node in the quadtree.