Analysis and applications of hierarchical data structures
C. H. Ang · 1990
In this thesis, we analyze some of the variants of the region quadtree data structure, namely the PR (point region) quadtree and the PM (polygonal map, i.e., line segments) quadtree, we describe a new region expansion algorithm on region quadtrees, and we study the implementation of a random quadtree generator. The first part of the thesis is devoted to the analysis of the PR quadtree. We propose a method that can predict the node distribution of a PR quadtree. The predicted node distribution exhibits two characteristics termed the aging and phasing phenomena. This method is further improved by using a Poisson model. Moreover, the model can be used to explain the aging and phasing phenomena analytically instead of empirically. The second part of the thesis contains an analysis of the PM quadtree. Based on some results in geometric probability, we apply the same method that is used to predict the node distribution of a PR quadtree to predict the node distribution of a PM quadtree. We also find its average storage utilization. In the third part of the thesis, we describe a new region expansion algorithm for a plane image encoded in a quadtree. Two new concepts, namely, merging clusters and vertex sets, are introduced. They are the difference between the new algorithm and the previous approaches. We discuss the extension of the new algorithm to octrees, study the performance of various region expansion algorithms, and derive their time complexities. We also compare the concepts of a vertex set, an X-Y convex hull, and the maxima of a set of vectors. Finally, we study the implementation of a random quadtree generator using three different probability models. Although none of the three generators implemented measures up to the criteria for a good random quadtree generator, the study of the implementation does shed some light on the formation of a random image.