CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
Implementation of Feature Selection Using Correlation Matrix in Python

Ahmad Farhan AlShammari
Random Articles
Reseach Article

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

by Safwan W. Qasem, Ameur A. Touir
journal cover thumbnail

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, Ameur A. Touir . Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding. International Journal of Computer Applications. 132, 8 ( December 2015), 22-30. DOI=10.5120/ijca2015907501

@article{ 10.5120/ijca2015907501,
author = { Safwan W. Qasem, Ameur A. Touir },
title = { Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding },
journal = { International Journal of Computer Applications },
issue_date = { December 2015 },
volume = { 132 },
number = { 8 },
month = { December },
year = { 2015 },
issn = { 0975-8887 },
pages = { 22-30 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume132/number8/23615-2015907501/ },
doi = { 10.5120/ijca2015907501 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:28:48.250367+05:30
%A Safwan W. Qasem
%A Ameur A. Touir
%T Cardinal Neighbor Quadtree: a New Quadtree-based Structure for Constant-Time Neighbor Finding
%J International Journal of Computer Applications
%@ 0975-8887
%V 132
%N 8
%P 22-30
%D 2015
%I 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.
Index Terms

Computer Science
Information Sciences

Keywords

CN-Quadrees Image coding neighbor finding.

Powered by PhDFocusTM