urbane diction art

quadtree

The quad-tree is a way to reoganize a rectangular grid of N x M cells, determined by (N + 1) horizontal lines and (M + 1) vertical lines. (Correspondingly, the segment tree is a way to organise N contiguous intervals.) To simplify the discussion, we assume that N = M = 2k. The quad-tree T is a quaternary tree where with each node we associate a 2i x 2i portion (called a 2i-square) of the grid (i = 0, 1, …, k). The 2i-square associated with a given node v of T (for i > 0) is subdivided into four 2i-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 v. The construction is initialized by associating the entire grid with the root of T, and terminates when the quadrisection process yields 20-squares (the leaves of T). Since T has N2, its construction takes O(N2) time and uses O(N2) space.

We now examine how a rectange R can be stored in a quad-tree. The basic grid is formed by the 2N abscissae and 2N ordinates of the given N rectangles, and the quad-tree T is constructed on this grid.