CFP last date
20 June 2024
Reseach Article

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

by Safwan W. Qasem, Ameur A. Touir
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.