# quadtree

The

quad-treeis a way to reoganize a rectangular grid ofN x Mcells, determined by(N + 1)horizontal lines and(M + 1)vertical lines. (Correspondingly, the segment tree is a way to organiseNcontiguous intervals.) To simplify the discussion, we assume thatN = M = 2. The quad-tree^{k}Tis a quaternary tree where with each node we associate a2portion (called a^{i}x 2^{i}2-square) of the grid (^{i}i = 0, 1, …, k). The2-square associated with a given node^{i}vofT(fori > 0) is subdivided into four2-squares by vertical and horizontal bisections; each of these four squares (referred to as NW, NE, SE, and SW quares) is associated with one of the four offsprings of^{i}v. The construction is initialized by associating the entire grid with the root ofT, and terminates when the quadrisection process yields2-squares (the leaves of^{0}T). SinceThasN, its construction takes^{2}O(Ntime and uses^{2})O(Nspace.^{2})We now examine how a rectange

Rcan be stored in a quad-tree. The basic grid is formed by the2Nabscissae and2Nordinates of the givenNrectangles, and the quad-treeTis constructed on this grid.