QUADTREE WITH QUADRATIC STORAGE Hyun-Chan Lee Tony C. Woo Department of Industrial & Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 Technical Report 86-29 March 1987

Quadtree with Quadratic Storage Hyun-Chan Lee Tony C. Woo Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 March 1987

<Abbreviated Title> Quadratic Quadtree <Mailing Address> Tony C. Woo Department of Industrial and Operations Engineering The University of Michigan Ann Arbor, Michigan 48109-2117 ii

<Key Phrases> Quadtree, Data Structure, Representation Method, Space Efficiency, Pattern Recognition, Computer Graphics, Algorithm. iii

Abstract In addition to being an approximation, existing quadtree methods require a large storage. We develop a new finite branching quadtree method which reduces the storage requirements from exponential to polynomial and guarantees an exact representation of the original object. These are made possible by adopting a new set of termination conditions that ensure finiteness of the quadtree during the subdivision. This new data structure is analysed theoretically and tested empirically. For space complexity, we analyse its best case, worst case, and average case. Given an n-gon, we show the expected number of nodes in our quadtree is O(n ). For time complexity, we again analyse the best, worst, and average cases for constructing such a quadtree and find the average to be O(n2). Finally, random n-gons are generated as test data. We find the regression equation for the number of nodes in a 2 quadratic to be N = 0.136n + 2.148n + 15.461. For construction time CT, we find CT = 1.147N - 18.535. iv

List of Symbols CT: Construction time of a quadtree. DEN: Double-edge node. e: An edge. E[-]: Expected value. f(-): Probability distribution function. G[]: T[.] - S[-]. H: Height of a quadtree. HN: Homogeneous node. KO,K: Convex sets in 2D, quadrants. L: Length of a line segment. MEN: Multi-edge node. n: Total number of edges in a polygon. N: Total number of nodes in a quadtree. NTN: Non-terminal node. PO'P1: Perimeter of convex set K0 or K1. Pr{.}: Probability. S[ ]: Average space complexity. SEN: Single-edge node. T[.]: Time complexity. U,W: Random variables. v: A vertex. [X,X2): X domain of a quadrant ranging from X1 to X2. [Y1,Y2): Y domain of a quadrant ranging from Y1 to Y2. v

1. Introduction The quadtree method is widely used in image processing and pattern recognition [2,4,5,8,10,11,12,15,18,19,20]. Its popularity is understandable when one considers its elegance. To obtain a quadtree for a 2D object, one starts with a quadrant which contains the entire object. If the quadrant under consideration is completely within or completely outside the object, it is left alone. Otherwise, the quadrant is subdivided into four quadrants each of which is treated similarly. The subdivision continues recursively until all the quadrants are completely within or completely outside the object, or a quadrant of some pre-specified size is reached. Some terms related to a quadtree are helpful. A node in a quadtree 2 is a quadrant in the Euclidean space E. When a quadrant is completely within a given object it is a black node. A quadrant which is completely outside the object is a white node. Because of the homogeneity of their colors within a quadrant, black and white nodes will be referred to as homogeneous nodes. A quadrant which is subdivided into four quadrants is a non-terminal node. A quadrant of the minimal allowed size is a minimum-resolution quadrant. A quadrant which reaches the size of minimum-resolution and is neither a black node nor a white node is a don't-care node. In a quadtree, homogeneous nodes and don't-care nodes are terminal nodes. The number of subdivisions to reach a minimum-resolution quadrant is the height of a quadtree. The condition which prevents a quadrant from further subdivisions is a termination condition for constructing a quadtree. We will call this kind of quadtree construction and representation method the Binary

method. A major advantage of the Binary method is the simplicity of the Boolean operations on a quadrant: intersection, union, difference, and complement. The intersection operation may be used for collision detection. The union, difference, and complement operations are commonly used in CAD for shape description. All Boolean operations on a quadrant can be performed in constant time. However, a Binary quadtree has a maximum of (4(H+)-1)/3 nodes, where H is the height of the quadtree. Thus, a major disadvantage of the Binary method is the exponential data storage requirement. Because of the sheer volume of data to compute on, even if the operations on a quadrant can be done in constant time, processing on a Binary quadtree-encoded object is not necessarily fast overall. To reduce the storage requirement, there are two approaches. The first approach is to develop a more storage-efficient data structure while maintaining the same termination conditions. Instead of using a tree structure with homogeneous nodes, an array is used to store black nodes only [3,7,19]. The elements of the array are represented by quaternary integers. This method reduces the storage by as much as the total storage for non-terminal nodes and white nodes. The number of non-terminal nodes in a quadtree can be estimated by (N-1)/4, where N is the total number of nodes in a quadtree in the Binary method. If we assume that the number of black nodes and the number of white nodes are the same on the average, the expected number of black nodes is (3N+1)/8. Therefore, reduction in the number of nodes over the Binary method is about 62%. The second approach is to reduce the storage requirements by 2

introducing more conditions to terminate the subdivision before a quadrant becomes homogeneous. To do so, edge and gray nodes are used as terminal nodes in addition to black and white nodes. An edge node is a quadrant which includes one edge. A gray node is a minimum-resolution quadrant which may include more than one edge. A reduction of 55%-65% in the number of nodes over that from the Binary method is possible. This is supported by experiments involving a polygon of 20 edges and the height of a quadtree is restricted to eleven [2]. Note that minimumresolution is invoked as a terminal condition in this approach as well. While storage is still a concern, another disadvantage of the existing methods is that a quadtree is inherently an approximation. The inexactness of representation and the large storage requirement of the existing quadtree methods come from the minimum-resolution termination condition (without which, the existing methods will not terminate. Because, on the boundary or at the vertices, the subdivision would continue forever.) To overcome these two disadvantages - storage and approximation, we propose a new finite branching quadtree representation. In our method, we use a new set of termination conditions to ensure finiteness without using the notion of minimumresolution. As a result, we achieve the goals of compactness in storage and exactness in representation. To visualize the effectiveness of the new termination conditions, a comparison of methods is illustrated in Figure 1. In the figure, quadtrees generated by the Binary method, by the Ayala, Brunet, Juan, and Navazo (ABJN) method [2], and by the new method are illustrated with a randomly generated polygon of 20 edges. To simulate finite branching 3

in the first two methods, we set the height to 6 which is the height of the quadtree in Figure l(c). For the Binary method, the quadrants are "clustered" on the boundary of the polygon. For the ABJN method, they are clustered at the vertices. By comparison, the quadrants by the new method are more "balanced" and "sparse" than these two methods. <Insert Figure 1> In Section 2, the new quadtree representation method is explained along with the data structure and the algorithm for constructing the quadtree. In Section 3, the space complexity of a quadtree by the new method is analyzed. In Section 4, the time complexity of the algorithm for constructing such a quadtree is analyzed. In Section 5, experimental results are shown. 4

I~~~~ 4 I ~~~~~~~~~~~~~~I tF9 _ _r a " P _? _ d an~~~~~~~~~ (a) Binary method (b) ABJN method (c) New method Figure 1. Comparison of Quadtrees

2. Finite Branching Quadtree 2 A quadrant is a subset of the Euclidean space E. The domain of a quadrant is defined as [X1,X2) x [YY2) c E, where X1 and X2 are the minimum and maximum X-coordinates of the quadrant, respectively; similarly, for the Y-coordinates. Note that we use an open set to include only one half of the boundary of the quadrant as the domain to avoid overlap. To terminate the subdivision without minimum-resolution, we provide a condition that ensures finite subdivision on the boundary and at the vertices. We allow a quadrant to contain two edges that intersect at a vertex. (Refer to quadrant ql in Figure l(c).) Two other types of terminal nodes are needed in addition to black and white nodes. One is a single-edge node, which corresponds to a quadrant that contains one edge. (The quadrant q2 in Figure l(c) is an example.) The other is a double-edge node, which corresponds to a quadrant that contains two edges. (See q3 and ql in Figure l(c).) We also allow the special case when a vertex is on the boundary of a quadrant that does not belong to the domain of the quadrant. This is illustrated in Figure 2(a). Our double-edge node ensures the finite termination of subdivision without minimum-resolution. In short, the termination condition for the finite quadtree of a simple polygon is to divide the 2D Euclidean space into quadrants until a quadrant contains a maximum of two edges. <Insert Figure 2> The termination conditions for a non-simple polygon are different from those for simple polygons as described in the preceding paragraph. 5

(a) Double-edge node (b) Multi-edge node Figure 2. A Vertex on the Boundary

A polygon is simple if no two non-consecutive edges share a vertex. Otherwise, the polygon is non-simple [14]. The need for representing a non-simple polygon comes from projection and hidden-line removal in computer graphics. If we represent a projected object only by its boundary (a simple polygon) as illustrated in Figure 3, we do not have a representation of the inside. Even in two dimensions, we need to consider quadtrees for simple and for non-simple objects. <Insert Figure 3> For a non-simple polygon, we need to add one more termination condition since there can be any number of edges incident to a vertex. Subdivision is terminated if a quadrant contains a set of edges that are incident to one vertex which is inside or on the boundary of the quadrant. See Figure 2(b). Such a quadrant corresponds to a multi-edge node in a quadtree. We summarize by comparing the terminal nodes of three methods: the Binary method, the ABJN method, and our new method, in Figure 4. <Insert Figure 4> The data structure for a quadtree is given in Table 1, which is described in Pascal. To indicate the inside of a simple polygon, we use the edge equation in a form of AX + BY + C > 0 by storing the coefficients A, B, and C. For a non-simple projected object, we record the number of faces of the 3D object to be projected in addition to the edge equations. 6

/A I II 4-7 I L A. 1.,,' l. l' I I I I I I I I I I I I I I I I I I III I I, I I'I, I F II 00 I #. 0 - - - -L 71 z117 * I (a) 3D object (b) Projected boundary (a simple polygon) (c) Projected 2D object (a non-simple polygon) Figure 3. Projection of a 3D Object onto 2D Screen

multi-edge node any size B_ gray terminal node minimum-resolution double-edge node any size don't-care node minimum-resolution edge node any size single-edge node any size wht rgrynd U white or black node any size (a) Binary method white or black node any size (b) ABJN method white or gray node any size (c) New method Figure 4. Comparison of Terminal Nodes

<Insert Table 1> The algorithm for constructing a quadtree using the four types of termination conditions in Figure 4(c) and the data structure in Table 1 is given as Algorithm QuadtreeConstruction. In the algorithm, the procedure Check Type examines Edges, an array containing the number of edges in the parent node of the quadrant currently under consideration, and decides the Type for the current quadrant based on the number of edges, Num_edges, in it. The procedure Subtree(Q) creates four children for the non-terminal node Q. The four children LB, RB, LT, and RT represent the left-bottom, right-bottom, left-top, and right-top quadrants, respectively. In this algorithm we omit the process of identifying whether a homogeneous node HN is a black or white node. (This can be done by traversing the constructed quadtree once. Therefore, it does not effect the time complexity of the construction algorithm.) <Insert Algorithm Quadtree Construction> 7

Type Node Set = (HN,SEN,DEN,MEN,NTN); Vertex Record = Record X Co: Real; Y Co: Real; End; Vertex_Array = Array[1..TotVertices] of VertexRecord; Edge_Record = Record First Vertex: Integer; Second Vertex: Integer; A,B,C: Real { coefficients of AX + BY + C > 0 } End; Edge_Array = Array[l..Tot_Edges] of Edge_Record; Edge_List = Array[1..Tot_Edges] of Integer NodePTR = tNode Record; NodeRecord = Record Parent: Node PTR Case Node Type: Node Set of HN: homogeneous node } ( Leaf: Boolean ); SEN: { single-edge node } (EG: Integer ); DEN: { double-edge node } ( E1,E2: Integer ); MEN: { multi-edge node } ( ESET: Edge List ); NTN: { non-terminal node T ( LB,RB,LT,RT: Node PTR ); End; Table 1. Data Structure for a Quadtree

Algorithm QuadtreeConstruction(Q,Edges,Num_Edges,X,Y,Scale) Begin Check Type(Edges,NumEdges,X,Y,Scale,Type) Case Type of HN: Q.NodeType < — HN SEN Qt.NodeType < — SEN Qt.EG < — Edges[l] DEN: Q.NodeType < — DEN Qt.El < — Edges[l] Qt.E2 < — Edges[2] MEN: Qt.NodeType < — MEN For i < — 1 to Num_Edges Do Qt.ESET[i] < — Edges[i] NTN:Qt.NodeType < — NTN Scale < — Scale / 2 Subtree(Q) QuadtreeConstruction(Qt.LB,Edges,NumEdges,X,Y,Scale) X < — X + Scale Quadtree_Construction(Qt.RB,EEdges,Nu EdgeX,Y,Scale) X < — X - Scale Y < — Y + Scale Quadtree_Construction(Qt.LT,Edges,NumEdges,X,Y,Scale) X < — X + Scale QuadtreeConstruction(Qt.RT,Edges,NumEdges,X,Y,Scale) End { Case } End { Algorithm }

3. Analysis of Space Complexity In this section, based on the new termination conditions we analyze the space complexity. The analysis consists of three cases: the best case, the worst case, and the average case. We use the symbol N for the total number of nodes in a quadtree corresponding to a given polygon with n edges. The best case, which is shown in Figure 5(a), occurs when every terminal node is a double-edge node. If H is the height of a quadtree, then in the best case H is log4n. The total number of nodes N thus is: N = 4 = (4.4H-1)/3 = 4n/3 - 1/3. i=O Therefore, the best case space complexity of a quadtree is linear in n, the total number of edges of a polygon. <Insert Figure 5> The worst case happens when two vertices (or one vertex and a nonincident edge) are very close. This is shown in Figure 5(b). If the edges at the lower-left corner of the figure and those at the upperright corner become shorter and closer to their respective corners, more and more nodes will be needed. In this worst case, the number of nodes of a quadtree would not depend on the number of edges n. Instead, it depends on the minimum distance between a vertex and an edge to which it is not incident. The following lemma gives us an idea about the maximum possible height of the quadtree. Lemma 1 The maximum possible height of a quadtree is the smallest 8

(a) The best case (b) The worst case Figure 5. The Best and the Worst Case of Space Complexity

integer which is greater than: log2(maxsize / mindistance) + 3/2 where max_size is the size of the largest quadrant and min_distance is the minimum among the distances from a vertex to non-incident edges. [Proof] The size s of the smallest quadrant is at most min distance / 2/2. When a vertex v and an edge e, which determine mindistance, lie diagonally in a quadrant, the size of the quadrant is min_distance / /2. This situation is illustrated in Figure 6(a). The size of the smallest quadrant is one half of the value since we need one more subdivision as shown in Figure 6(b). Therefore, the maximum possible height of a quadtree generated by the new method is the smallest integer which is greater than: log2(maxsize / (mindistance / 2/2)) = log2(maxsize / min_distance) + 3/2 where max_size is the size of the quadrant containing the entire object as shown in Figure 6(c). ~ <Insert Figure 6> The reason we say maximum possible height is that even when a vertex is close to an edge or when an edge is short, the maximum height may be less than that stated in Lemma 1. The situation is illustrated in Figure 6(d). The quadtree in Figure 6(c) has maximum possible height of 5. The same polygon translated by a small amount yields a quadtree of height 2, which is less than the maximum possible height. For the average case analysis of space complexity of a quadtree, we 9

e I H/ I \I I'" S V (a) (b) e Ii X I lw.1 LA I i maxsize I I maxsize I (c) (d) Figure 6. Maximum Possible Height of a Quadtree

employ a known result from geometric probability [21,22] without duplicating its proof. Lemma 2 Let K1 be a convex set with perimeter of length P1 contained in another bounded convex set K0 with perimeter of length P0. The probability that a random line intersects K1, if it is known to intersect K0, is P1/P0. <Insert Figure 7> An illustration of Lemma 2 is given in Figure 7. If we draw a random line which intersects the larger quadrant K0, then the probability that the line also intersects the smaller quadrant K1 is 1/2. However, an edge of a random polygon is only a subset of a random line since the two endpoints (vertices) of the edge are assumed to be uniformly randomly distributed on the line. Making this observation, we can estimate the average length of an edge. Lemma 3 The average length of an edge, given the length L of a line segment on which it lies, is L/3. [Proof] The average length of an edge is: E[|W-Ul] = E[W-UIW>U]Pr{W>U} + E[U-WlU2W]Pr{U2W} where U and W are random variables representing the two endpoints of an edge lying in the given line segment, and E[.] and Pr{*} denote the expectation and probability, respectively. Let f(.) be a probability distribution function. Then the first term on the right-hand side is: E[W-U W>U]Pr{W>U} 10

Figure 7. Illustration of Lemma 2

LL = Pr{W>U} Sf(w-u)f(u,w)/Pr{W>U}dwdu Ou LL = ff(w-u)f(u)f(w)dwdu Ou 2LL = (1/L ) ff(w-u)dwdu Ou = (1/L2)(L3/6) = L/6. With a similar derivation, we get E[U-WIU>W]Pr{U>W} = L/6. Therefore, the average length of an edge is L/3. ~ Using Lemma 2 and Lemma 3, we arrive at the upper bound for the expected number of nodes for a quadtree. Theorem 1 The expected number of nodes of a quadtree corresponding to a polygon is bounded in space O(n2). [Proof] If we extend each edge of a polygon to a line, then the probability that a line intersects a quadrant K of a parent quadrant K0, given that the line intersects K0, is 1/2 by Lemma 2. Therefore, the expected number of lines intersecting K1, when the number of lines intersecting K0 is n, is n/2. Hence, the average space complexity S(n) of the new method can be calculated by the following recursive relation: S(0) = S(1) = S(2) = 1, S(n) = 4S(n/2) + 4. Here, the constant 4 comes from the fact that a quadrant produces 4 sub-quadrants if it is subdivided. The solution of this recursive 11

relation, i.e. the expected space complexity of our quadtree method, is O(n ) [1]. Since an edge is shorter than its extended line segment by Lemma 3, the above result is an absolute upper bound on the expected space complexity. I 12

4. Time Complexity of the Construction Algorithm We next analyze the time complexity of constructing a quadtree. The analysis again involves three cases: the best case, the worst case, and the average case. In the algorithm presented in Section 2, the major element which determines its time complexity is the number of edges examined for each node. By comparing the number of nodes generated and the accumulated number of edges examined, we can get the time complexity T of the algorithm in terms of N, the total number of nodes in a quadtree. Lemma 4 The best case of the time complexity of the algorithm for constructing a quadtree is O(N). [Proof] If the average number of edges examined per node is constant, then T(n) is O(N). Such a case does exist, as illustrated in Figure 5(b). Whenever a subdivision is necessary, we examine a constant number of edges, 3 in this example, and produce 4 more nodes. Therefore, the more such subdivisions there are, the closer the average number of edges examined per node is to some constant, 3/4 in this example. Hence, the best case time complexity is O(N). ~ Lemma 5 The worst case of the time complexity of the algorithm for constructing a quadtree is 0(N ). [Proof] The maximum possible average number of edges examined per node is O(n). If N is O(n), the total number of edges examined is O(n ). T(n) is therefore 0(N ) in the worst case. Now, we show 13

the existence of such a case as illustrated in Figure 8. In the figure, whenever there is a subdivision, a vertex is no longer under consideration. In this case, we can show that: N = 2n + 3 = O(n), T(n) = n + 9n - 9 = N/4 + 3N - 81/4 = O(N). Hence, the worst case time complexity is 0(N ). ~ <Insert Figure 8> Theorem 2 The average time complexity of the algorithm for constructing a quadtree is O(N). [Proof] On the average, the accumulated number of edges examined which is equivalent to the time complexity T(n) is: T(2) = T(1) = T(0) = 0, T(n) = 4T(n/2) + 4n. Here, the constant 4 comes from the fact that a quadrant produces 4 sub-quadrants if it is subdivided. The solution of the above recursive relation is T(n) = 0(n ). To prove that T(n) and S(n) have the same complexity of 0(n ), let G(n) be T(n) - S(n). Then, G(n) = 4G(n/2) + 4(n - 1). 2 The solution of this recursive relation is also 0(n ). Having shown that the average T(n) is 0(n ), we recall the definition that there are N nodes in a quadtree. Therefore, the average time complexity of the quadtree construction algorithm is linear in N. ~ 14

Figure 8. The Worst Case in Time Complexity

5. Experimental Results We have performed experiments to verify the theoretical storage and time complexities of the construction algorithm. The hardware used for the experiment is Amdahl 470V/8 at the University of Michigan in Ann Arbor, Michigan. To compare our method to the Binary methods, we use randomly generated polygons. (As there is no provision for handling non-simple polygons by existing methods, we restrict our comparison to using simple polygons.) A method to generate a random simple polygon is as follows. First, we generate uniformly random angles around a point which is located in the center of a quadrant. Then, we generate radii based on the assumption that a radius is distributed uniformly from zero to the one half of the width of the quadrant. By joining the vertices in sorted angular order, we get a random polygon that is simple. 5.1 Space Complexity A comparison of the number of nodes generated by our method and by the Binary method is illustrated in Figure 9. The result shows, for example, that the number of nodes generated by our method is strictly less than that of the Binary method if the height is greater than 6 and the number of edges is less than 100. <Insert Figure 9> A scatter plot of the number of nodes generated against the number of edges of a given polygon is given as Figure 10. In the figure, the numbers indicate the frequency of occurrences and'*' represents an 15

. "0 0 CCD a) 0' a) V'0 0) 0 C> E z o Cr 0 i 2 i o) \ \ 1 \ ^~~~~~~~~~~~ \ \ I 1 ^~~~~~~~~~~~~~~~L 0 0 0 0 L() N sepou jo -ON

occurrence of once. From the data, we find the regression equation to be: N = 0.136 n2 + 2.148 n + 15.461. F test for the above regression relation shows that we can conclude with a confidence level of 0.99. The coefficient of multiple determination 2 R is 0.989. This result supports Theorem 1 which states that the number of nodes is quadratic in the number of edges. <Insert Figure 10> 5.2 Time Complexity The experiment involves a comparison between the number of nodes generated and the construction time. The average number of edges examined per node is also calculated. The scatter plot of the construction time CT against the number of nodes generated N is given in Figure 11 with the same legend. We find the regression equation to be: CT = 1.147 N - 18.535. F test for the above regression relation shows that we can conclude with a confidence level of 0.99. The coefficient of simple determination R is 0.998. This result supports Theorem 2 which asserts the linear relation between time and the number of nodes. <Insert Figure 11> The average number of edges examined per node is plotted against the number of edges of a given polygon in Figure 12. The values range from 4.2 to 5.0 and they have a tendency to be strictly less than 5. 16

No. of nodes N 2000.0 + 1600.0 + 1200.0 + 800.0 + 400.0 + 0.0 + 0 2 * ~ 22~ * ** ** * * * 2 * * * 22 * *22 *** *2,2 2*2* 222* 22 *22 22222* 2** +.0 20.0 40.0 60.0 80.0 100.0 —-— +..+..+.+.0 20.0 40.0 60.0 80.0 100.0 No. of edges n Figure 10. Scatter Plot: Number of Nodes versus Number of Edges

Construction time CT (in miliseconds) 2500.0 + * 2000.0 + + * * ** 1500.0 + 2 **2 + * * 23 1000.0 + 4 32 4* + **~ 4* *3 500.0 + 62 4* 23* + 22* 422 445 0.0 +*5 +.... —-+......+....+....+ —---— + I-....-+....+....+ 0.0 400.0 800.0 1200.0 1600.0 2000.0 No. of nodes N Figure 11. Scatter Plot: Construction Time versus Number of Nodes

This result also supports Theorem 2. <Insert Figure 12> 17

A, 5.0 0 4.5 0. 4.5 0 cm 6 z 4.0 20 40 60 80 100 No. of edges Figure 12. Average Number of Edges Examined per Node against Number of Edges

6. Conclusion By using the new termination conditions, we are able to reduce the storage for a quadtree from exponential to quadratic in n, on the average, for a given n-gon, yet offer exact representation. The construction time for such a quadtree is quadratic in n as well. While our method retains much of the simple elegance of the existing quadtree methods, our analysis confirmed by experiments offer a new lower bound in time and storage to theoreticians and practitioners alike. 18

References [1] A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1974. [2] D. Ayala, P. Brunet, R. Juan, and I. Navazo, Object representation by means of nonminimal division quadtrees and octrees, ACM Trans. Graphics 4, pp. 41-59, 1985. [3] H. H. Atkinson, I. Gargantini, and T. R. S. Walsh, Filing by quadrants and octants, Computer Vision, Graphics, and Image Processing 33, pp. 138-155, 1986. [4] B. B. Chaudhuri, Applications of quadtree, octree, and binary tree decomposition techniques to shape analysis and pattern recognition, IEEE Pattern Analysis and Machine Intelligence PAMI7, pp. 652-661, 1985. [5] C. R. Dyer, A. Rosenfeld, and H. Samet, Region representation: boundary codes from quadtrees, Comm. ACM 23, pp 171-179, 1980. [6] C. E. Eastman, Representation for space planning, Comm. ACM 13, pp. 242-250, 1980. [7] I. Gargantini, Linear octrees for fast processing of three dimensional objects, Computer Graphics and Image Processing 20, pp. 365-374, 1982. [8] G. M. Huster and K. Steiglitz, Operations on images using quadtrees, IEEE Trans. Pattern Analysis and Machine Intelligence PAMI-1, pp. 145-153, 1979. [9] C. L. Jackins and S. L. Tanimoto, Octrees and their use in representing 3D objects, Computer Graphics and Image Processing 14, pp. 249-270, 1980. 19

[10] C. L. Jackins and S. L. Tanimoto, Quadtrees, octrees, and k-trees: a generalized approach to recursive decomposition of Euclidean space, IEEE Trans. Pattern Analysis and Machine Intelligence PAMI5, pp. 533-539, 1983. [11] L. P. Jones and S. S. Iyengar, Space and time efficient virtual quadtrees, IEEE Trans. Pattern Analysis and Machine Intelligence PAMI-6, pp. 244-247, 1984. [12] A. Klinger and C. D. Dyer, Experiments on picture representation using regular decomposition, Computer Graphics and Image Processing 5, pp.68-105, 1976. [13] D. Meagher, Geometric modeling using octree encoding, Computer Graphics and Image Processing 19, pp. 129-147, 1982. [14] F. P. Preparata and M. I. Shamos, Computational Geometry, Springer-Verlag, New York, 1985. [15] C. Puech and H. Yahia, Quadtrees, octrees, and Hyperoctrees: a unified analytical approach to tree data structures used in graphics, geometric modeling and image processing, ACM Proc. Symposium on Computer Graphics, pp. 272-280, 1985. [16] H. Samet, Region representation: quadtrees from boundary codes, Comm. ACM 23, pp. 163-170, 1980. [17] H. Samet, Connected component labeling using quadtrees, J. ACM 18, pp. 487-501, 1981. [18] H. Samet, The quadtree and related hierarchical data structures, ACM Comput. Survey 16, pp. 187-260, 1984. [19] H. Samet, Data structure for quadtree approximation and compression, Comm. ACM 28, pp. 973-993, 1985. [20] H. Samet and R. E. Webber, On encoding boundaries with quadtrees, 20

IEEE Trans. Pattern Analysis and Machine Intelligence PAMI-6, pp. 365-369, 1984. [21] L. A. Santalo, Integral geometry and geometric probability, Addison-Wesley, Reading, Mass., 1976. [22] M. Tamminen, Performance analysis of cell based geometric file organizations, Computer Vision, Graphics, and Image Processing 24, pp. 160-181, 1983. [23] M. Yau and S. N. Srihari, A hierarchical data structure for multidimensional digital images, Comm. ACM 26, pp. 504-515, 1983. 21