Abstract

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.

References

• Schrack G 1992 Finding Neighbors of Equal Size in Linear Quadtrees and Octrees in Constant Time, CVGIP: Image Understanding, 55: 221-230.
• Aizawa K, Motomura K, Kimura S, Kadowaki R and Fan J 2008 Constant Time Neighbor Finding in Quadtrees: An Experimental Result, in: Proc. 3rd International Symposium on Communications, Control and Signal Processing, Malta.
• Aizawa K and Tanaka S 2009 A Constant-Time Algorithm for Finding Neighbors in Quadtrees, IEEE Trans. Pattern Analysis and Machine Intelligence, 31(7), 1178-1183.
• Finkel R A and Bentley J L 1974 Quad Trees: A Data Structure for Retrieval on Composite Keys, Acta Informatica, 4: 1-9.
• Samet H and Webber R E 1985 Storing a Collection of Polygons Using Quadtrees, ACM Transactions on Graphics 4(3): 182-222.
• Samet H 1985 A Top-Down Quadtree Traversal Algorithm, IEEE Trans. Pattern Analysis and Machine Intelligence 7: 94-98.
• Fuhrmann D R 1988 Quadtree Traversal Algorithms for Pointer-Based and Depth-First Representations, IEEE Trans. Pattern Analysis and Machine Intelligence, 10: 955-960.
• Vörös J 1997 A Strategy for Repetitive Neighbor Finding in Images Represented by Quadtrees, Pattern Recognition Letters, 18:955-962.
• Frisken S F and Perry R N 2002 Simple and Efficient Traversal Methods for Quadtrees and Octrees, The Journal of Graphics Tools, 7(3): 1-11.
• Gargantini I 1982 An Effective Way to Represent Quadtrees, Comm. ACM, 25: 905-910.
• Samet H 1982 Neighbor finding techniques for images represented by quadtrees, Computer Graphics and Image Processing, 18: 35-57.
• Kadowaki R, Motomura K, Ohkura S and Aizawa K 2010 Graphs Representing Quadtree Structures using Eight Edges, Proc. Int. Symposium on Communications, Control and Signal Processing, Cyprus.
• Samet H 1984 The quadtree and related hierarchical data structures, ACM Computing Surveys. 16(2): 187-260.
• Samet H 1990 Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, Addison-Wesley, Boston.
• Klinger, A., and M.L. Rhodes, 1979. Organization and access of image data by areas, LEEE Trans. Pattern Anal. Mach. Lntell., PAMI-1:5& 60.
• Yoder R and Bloniarz P 2006 A Practical Algorithm for Computing Neighbors in Quadtrees, Octrees, and Hyperoctrees, Proc. Int. Conf. on Modeling, Simulation, and Visualization Methods, Las Vegas, USA.
• USC-SIPI Image Database, last accessed March 2015, http://sipi.usc.edu/database/,
• Hunter, G.M., and K. Steiglitz, 1979a. Operations on images using quad trees. IEEE Transactions on Pattern Analysis and Machine Intelligence,. 1, 2 (Apr.), 145-153.
• Hunter, G.M., and K. Steiglitz, 1979b. Linear transformation of pictures represented by quadtrees. Comput. Gr. Image Process. 10, 3 (July), 289-296.