1. Suppose we wish to solve the problem of, given data points in the
plane, listing all points contained in a query triangle.  We attempt to
solve it with the following data structure:

- We partition the points into a set of nested convex hulls:
  H_0 is the convex hull of the input, H_1 is the hull of the points
  other than the ones already vertices H_0, and in general
  H_i is the hull of the points other than the ones that are already
  vertices of some hull H_j for j<i.

- We store each convex hull separately, in a data structure that allows
  us to perform binary searches (e.g. a sorted array of its vertices).
  We do not use fractional cascading.

- To answer a query for the points in triangle T, we apply the
  following pseudocode:

  def query(T):
      for i in range(0, number of hulls):
          for each of the three lines L_0, L_1, L_2 on the boundary of T:
              use binary search on slopes to find the points p,q on H_i
                  that are farthest in each direction from L_j
              if p and q are on opposite sides of L_j:
                  use binary search on the two parts of the hull H_i between
                  p and q to find the two points where L_j crosses H_i

          split the hull H_i into paths at the (at most six) crossing points
          found above (or a single path if there are no crossing points)

          for each path into which H_i is split:
              if the first segment of the path is contained in T:
                  output all vertices of H_i in the path

          if none of L_0, L_1, and L_2 cross H_i and
                  no vertices of H_i were output:
              break

(a) Does this pseudocode correctly answer the range query? Why or why not?

(b) Does this query algorithm take an amount of time polynomial in log n
(where n is the number of data points) and in k (the size of the output)?
If so, what is the running time?  If not, explain why not.