1. (a) What is the maximum number of nodes that a kD-tree for n points can have, as a function of n? Include the nodes at all levels of the kD-tree hierarchy, not just the leaves.

Counting the empty rectangles at the leaf levels of the tree, we have a binary tree with n internal nodes (each internal node has to have one point on its split line) and n+1 leaves, for a total of 2n+1 nodes.

(b) What is the minimum number of nodes that a quadtree for n points can have, as a function of n?

A quadtree with one node can accomodate only one point. Each additional split in the quadtree produces four more nodes, but makes room for only three more points. So the minimum number of nodes is 4 floor((n-1)/3) + 1.

(c) Draw a set of 5 points, and a kD-tree for that set, that achieves the maximum number of nodes from part (a). Also draw a different set of 5 points, and a quadtree for that set, that achieves the minimum number of nodes from part (b).

Any five points not all on a line will work for part (a). For part (b), split the outer quadtree square and one of its children, and place the five points in five different squares out of the seven squares formed in this way.


2. Let L1 = 2, 3, 5, 7, 11, 13 ... be the sequence of prime numbers. Let L2 = 0, 4, 8, 12, 16, ... be the sequence of multiples of four. And let L3 = 1, 4, 9, 16, 25, 36, ... be the sequence of nonzero square numbers.

(a) List the first ten numbers in each of the three lists formed in a fractional cascading data structure for L1, L2, and L3.

Call the combined lists C1, C2, and C3. Then, in the order they are formed:

C3 = L3 = 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...
    the alternating subsequence 1, 9, 25, ... gets merged up
C2 = 1, 4, 8, 9, 12, 16, 20, 24, 25, 38, ...
    the alternating subsequence 1, 8, 12, 20, 25, ... gets merged up
C1 = 1, 2, 3, 5, 7, 8, 11, 12, 13, 17, ...

(b) Let q=10, and suppose that we wish to find in each input list Li the first number xi that is greater than or equal to q. Which numbers in the second and third of the fractionally cascaded lists would be examined as part of this query?

In C1, the search finds 11 as the first number >= q.

The entry for 11 in C1 points to 12 in C2, and we step back and compare q to 9. The result of this comparison is that we find 12 as the first number in C2 that is >= q.

The entry for 12 in C2 points to 16 in C3, and we step back and compare q to 9 again. The result of this comparison is that we find 16 as the first number in C3 that is >= q.

So the answer to the question is that we examine 9 and 12 in C2, and 9 and 16 in C3.