CIS 677: Homework 1, due about Sep. 29

Using the notation of lecture 2:

1. For boxes B and B', show that B and B' have nonempty intersection if and only min(B) dominates max(B'), and min(B') dominates max(B).
2. Prove the following: given point set S in the plane, show that if a point p of S yields no minima in S⁺⁺, S^+-, S^--, or S^-+, then that point is not extreme in S, that is, not a vertex of the convex hull.
3. In the lecture, and in section 10.3 of the text, a data structure is proposed for a set S of noncrossing line segments, so that given a box, the line segments meeting that box can be found quickly. Can that data structure be used to quickly find the segments of S that meet a given general line segment q?
4. 5.10a and b of the text: In some applications one is interested only in the number of points that lie in a range rather than in reporting all of them. Such queries are often referred to as range counting queries. In this case one would like to avoid paying the O(k) in the query time. [[k=A, the answer size]]
   1. Describe how a 1-dimensional range tree can be adapted such that a range counting query can be performed in O(log n) time. Prove the query time bound.
   2. Describe how d-dimensional range counting queries can be answered in O(log^dn) time, using the solution to the 1-dimensional problem. Prove the query time.
5. 10.1 of the text:
   In Section 10.1 we solved the problem of finding all horizontal line segments in a set that intersect a vertical segment. For this we used an interval tree with priority search trees as associated structures. There is also an alternative approach. We can use a 1-dimensional range tree on the y-coordinate of the segments to determine those segments whose y-coordinate lies in the vertical query segment. The resulting segments cannot lie above or below the query segment, but they may lie completely to the left or to the right of it. We get those segments in O(log n) canonical subsets. For each of these subsets we use an associated structure an interval tree on the x-coordinates to find the segments that actually intersect a query segment.
   1. Work out the details of this approach.
   2. Prove that the data structure correctly solves the queries.
   3. What are the bounds for preprocessing time, storage required, and query time for this structure? Prove your answers.
6. 10.6 of the text:
   Let I be a set of intervals on the real line. We want to be able to count the number of intervals containing a query point in O(log n) time. Thus the query time must be independent of the number of segments containing the query point.
   1. Describe a data structure for this problem based on segment trees, that uses only O(n) storage. Analyze the amount of storage, preprocessing time, and the query time of the data structure.
   2. Describe a data structure for this problem based on interval trees. You should replace the lists associated with the nodes of the interval tree with other structures. Analyze the amount of storage, preprocessing time, and the query time of the data structure.
7. 10.8 of the text:
   Segment trees can be used for multi-level data structures.
   1. Let R be a set of n axis-parallel rectangles in the plane. Design a data structure for R such that the rectangles containing a query point q can be reported efficiently. Analyze the amount of storage and the query time of your data structure. Hint: Use a segment tree on the x-intervals of the rectangles, and store canonical subsets of the nodes in this segment tree in an appropriate associated structure.
   2. Generalize this data structure to d-dimensional space. Here we are given a set of axis-parallel hyperrectangles--that is, [[boxes]]--and we want to report the hyperrectangles containing a query point.