1. Suppose we wish to build a data structure that stores a set of n three-dimensional points and answers queries requesting the number of points within an axis-parallel box. We are considering three multilevel data structures for this problem: (i) an outer data structure in the form of a binary search tree on the x-coordinates of all the points, each node of which stores an inner data structure in the form of a kD-tree on the y and z coordinates of its descendant points, and (ii) an outer data structure in the form of a kD-tree on the x and y coordinates of all the points, each node of which stores an inner data structure in the form of a binary search tree on the z coordinates of the points within its rectangle.
(a) How much space would data structure (i) use, and what is its query time?
(b) How much space would data structure (ii) use, and what is its query time?
(c) Can fractional cascading be applied to either of the two data structures? If so, what is the improved query time that would be obtained by using it?

2. Suppose we wish to store a set of two-dimensional points, and answer queries requesting the number of points within a specified axis-aligned right triangle. Show that a kD-tree may require Omega(n) time per query for this problem.