Balancing of Quad Tree using Point Pattern Analysis

Authors: Amitava Chakraborty, Sudip Kumar De, Ranjan Dasgupta

Abstract:

Point quad tree is considered as one of the most common data organizations to deal with spatial data & can be used to increase the efficiency for searching the point features. As the efficiency of the searching technique depends on the height of the tree, arbitrary insertion of the point features may make the tree unbalanced and lead to higher time of searching. This paper attempts to design an algorithm to make a nearly balanced quad tree. Point pattern analysis technique has been applied for this purpose which shows a significant enhancement of the performance and the results are also included in the paper for the sake of completeness.

Keywords: Algorithm, Height balanced tree, Point patternanalysis, Point quad tree.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078921

References:

[1] H. Samet, "The quadtree and related hierarchical data structures", ACM Computing Surveys 16, 2(June 1984), pp. 187-260.
[2] R. A. Finkel & J. L. Bentley, "Quad trees - A data structure for retrieval on composite keys", Acta Inform., vol. 4, no. 1-9, 1974.
[3] G. Keden, "The quad-CIF Tree: A data structure for hierarchical on lone algorithms", in Proc. 19th Design Automation Conf. , pp. 352-357, June 1982.
[4] Brown R. L. "Multiple storage quad tree : a simpler faster alternative to bisector list quad trees", " IEEE Trans. Computer Aided Design Vol CAD-5 pp 413-419, July 1986.
[5] W. Li, S. Legendre & K. Gardiner, " Two-layer quadtree: a data structure for high-speed interactive layout tools", International Conference Computer-Aided-Design, pp. 530-533, 1988.
[6] W. Ludo & D. Wim, " Quad List Quad Tree: A geometrical structure with improved performance for large region queries" Computer -Aided Design, Vol-8 March 1989.
[7] P. V. Srinivas & V.K. Dwivedi, " YAQT: Yet Another Quad Tree", IEEE Trans., pp. 302-309, 1991.
[8] S. J. Lu & Y. S. Kuo, " Multicell Quad Trees", IEEE Trans., pp. 147- 151, 1992.
[9] J. A. Orenstein, "Multidimensional tries used for associative searching",
[10] Information Processing Letters 14, 4(June 1982), 150-157.
[11] Pei-Yung Hsiao, "Nearly Balanced Quad List Quad Tree- A Data Structure for VLSI Lay out Systems", 1996 OPA(Overseas Publishers Association) Amsterdam B. V.
[12] Pei-Yung Hsiao & Lih-Der Jang, "Using a Balanced Quad List Quad Tree to speed Up a Hierarchical VLSI Compaction Scheme", IEEE, 1991.
[13] David O-Sullivan & David J. Unwin, " Geographic Information Analysis", John Wiley and Sons, 2002.
[14] Ralf Hartmut G├╝ting, "An Introduction to Spatial Database Systems", Special Issue on Spatial Database
[15] A. Klinger, Patterns and Search Statistics , in Optimizing Method in Statistics, J. S. Rustagi, Ed., Academic Press, New York, 1971, pp. 303- 337.
[16] H. Samet & R.E. Webber, " Storing a collection of polygons using quadtrees," ACM Transactions on Graphics 4, 3(July 1985), pp. 182- 222(also Proceedings of Computer Vision and Pattern Recognition 88, Washington, DC, June 1983,pp. 127-132).