You are to solve the following problem and turn in your solutiion at
the start of class on Tuesday, February 22, 2005.  This is to be your
own work and you are not supposed to discuss the solution with another
person.  You will be graded on this like an in class quiz.

QUESTION:  Consider the search for the two-dimensional range
(Bx:Ex],[By :Ey]) in a range priority tree.  The algorithm that we
outlined first finds the nearest common ancestor Q of By and Ey, and
the second step searches for ([Bx:Ex],[By:+infinity]) in the priority
search tree, say p, attached to the left child L of Q.  Note that p is
a superset of the objects that can satisfy the query.  Making use of
this observation, why can't we simplify the algorithm by descending as
many right links of the left child L of Q as possible until
encountering a nonleaf node S for which By is in the left subtree?
Similarly, for the third step of the algorithm, the subsequent search
is for ([Bx:Ex],[-infinity:Ey]) in the priority search tree, say p,
attached to the right child R of Q.  Again, we note that p is a
superset of the objects that can satisfy the query.  Making use of
this observation, why can't we simplify the search by descending as
many left links of the right child R of Q as possible until
encountering a nonleaf node S for which Ey is in the right subtree?