Call for Paper - July 2023 Edition
IJCA solicits original research papers for the July 2023 Edition. Last date of manuscript submission is June 20, 2023. Read More

Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding

Print
PDF
 
Download Full Text
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 132 - Number 8
Year of Publication: 2015
Authors:
Safwan W. Qasem, Ameur A. Touir
10.5120/ijca2015907501

Safwan W Qasem and Ameur A Touir. Article: Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding. International Journal of Computer Applications 132(8):22-30, December 2015. Published by Foundation of Computer Science (FCS), NY, USA. BibTeX

@article{key:article,
	author = {Safwan W. Qasem and Ameur A. Touir},
	title = {Article: Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding},
	journal = {International Journal of Computer Applications},
	year = {2015},
	volume = {132},
	number = {8},
	pages = {22-30},
	month = {December},
	note = {Published by Foundation of Computer Science (FCS), NY, USA}
}

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

  1. Schrack G 1992 Finding Neighbors of Equal Size in Linear Quadtrees and Octrees in Constant Time, CVGIP: Image Understanding, 55: 221-230.
  2. 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.
  3. 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.
  4. Finkel R A and Bentley J L 1974 Quad Trees: A Data Structure for Retrieval on Composite Keys, Acta Informatica, 4: 1-9.
  5. Samet H and Webber R E 1985 Storing a Collection of Polygons Using Quadtrees, ACM Transactions on Graphics 4(3): 182-222.
  6. Samet H 1985 A Top-Down Quadtree Traversal Algorithm, IEEE Trans. Pattern Analysis and Machine Intelligence 7: 94-98.
  7. Fuhrmann D R 1988 Quadtree Traversal Algorithms for Pointer-Based and Depth-First Representations, IEEE Trans. Pattern Analysis and Machine Intelligence, 10: 955-960.
  8. Vörös J 1997 A Strategy for Repetitive Neighbor Finding in Images Represented by Quadtrees, Pattern Recognition Letters, 18:955-962.
  9. 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.
  10. Gargantini I 1982 An Effective Way to Represent Quadtrees, Comm. ACM, 25: 905-910.
  11. Samet H 1982 Neighbor finding techniques for images represented by quadtrees, Computer Graphics and Image Processing, 18: 35-57.
  12. 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.
  13. Samet H 1984 The quadtree and related hierarchical data structures, ACM Computing Surveys. 16(2): 187-260.
  14. Samet H 1990 Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, Addison-Wesley, Boston.
  15. 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.
  16. 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.
  17. USC-SIPI Image Database, last accessed March 2015, http://sipi.usc.edu/database/,
  18. 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.
  19. Hunter, G.M., and K. Steiglitz, 1979b. Linear transformation of pictures represented by quadtrees. Comput. Gr. Image Process. 10, 3 (July), 289-296.

Keywords

CN-Quadrees; Image coding , neighbor finding.