1. Draw a set S of 15 points, a line L, and the kD-tree T of S, with the
   property that L crosses each of the line segments in T that partition
   a rectangle into two smaller rectangles. Can L be chosen to be
   vertical or horizontal? Why or why not?

2. We saw in class how to list all data points within a query rectangle
   efficiently, if the data are stored in a kD-tree. Describe how to
   perform the same queries for a quadtree. That is, given a quadtree on
   a set S of points, and a query rectangle R, describe how to use the
   quadtree to list all points of S that are inside R.

3. Which of the (uncompressed) quadtree and kD-tree is more
   space-efficient? Explain your answer.