1. Suppose that we have data consisting of a set of intervals, but for
each query we want to list the intervals that overlap (that is, have
nonempty intersection with) a query interval.  Describe how to use an
interval tree to answer these queries efficiently.


2. Suppose we wish to use a segment tree to maintain a dynamic set of
intervals (with a known set of interval endpoints) and answer queries
requesting the total length of the union of the intervals.

(a) For a segment s, let N(s) be the number of data intervals associated
with s, and let L(s) be the total length of the union of the segments
descending from s in the segment tree (including s itself) that have
nonzero values of N(s).  Give a formula for computing L(s) from the
values of N and L at s and its two children in the segment tree, and
conclude that these quantities can be maintained efficiently as
intervals are inserted and deleted in the segment tree.  How can we
compute the total length of the union of all the intervals from these
quantities?

(b) Suppose we are given a collection of n rectangles in the plane
(static, so we don't have to worry about insertions and deletions)
and we wish to compute the area of the union of the rectangles.
Describe how to solve this by a plane sweep algorithm using the dynamic
interval union length data structure of part (a).


3. In the lecture we described a data structure for point location
(given a collection of disjoint line segments in the plane, find the
first segment hit by a vertical ray from a query point) based on
combining a segment tree on the horizontal projections of the segments
with, for each node of the segment tree, a binary search tree on
vertically ordered line intervals associated with that segment.
Suppose we wish to use fractional cascading to speed up the queries in
this structure. Would it work better to cascade from the root of the
segment tree towards the leaves, or vice versa. (Hint: for which of
these two directions can you define a consistent vertical ordering of
the cascaded set of intervals associated with each segment?)