In this problem, we will consider how to use/modify range trees to answer a number of queries. In each case, the input is an n-element point set P in IRd . In each case, explain what points are stored in the range tree, what the various levels of the range tree are, and how queries are answered. Finally, justify your algorithm’s correctness and derive its storage and running time as a function of n. Note that you don’t have to re-copy entire pieces of pseudocode or proof - if it is the same as the one covered in class or the lecture notes or book, just say so! If it’s very close, you are welcome to discuss (in detail) only the differences with the version covered in class or the book.
In this problem, we will consider how to use/modify range trees to answer a number of queries. In each case, the input is an n-element point set P in IRd . In each case, explain what points are stored in the range tree, what the various levels of the range tree are, and how queries are answered. Finally, justify your
Note that you don’t have to re-copy entire pieces of pseudocode or proof - if it is the same
as the one covered in class or the lecture notes or book, just say so! If it’s very close, you
are welcome to discuss (in detail) only the differences with the version covered in class or the
book.
(a) A skewed rectangle is defined by two points q
− = (x
−, y−) and q
+ = (x
+, y+). The the
range shape is a parallelogram that has two vertical sides and two sides with a slope of
+1. The lower left corner is q
− and the upper right corner is q
+. The answer to the
query is the number of points of P that lie within the parallelogram. (In Figure 2(a),
the answer to the given query is 3.)
(b) In a vertical segment-sliding query (VSS), you are given a vertical line segment with
x-coordinate x0 and endpoints at y-coordinates y0 and y1, where y0 < y1. The answer
to the query is the point that is first hit if the segment is translated to the right. More
formally, among the points of P whose y-coordinates lie within the interval [y0, y1], the
answer is the point with the smallest x coordinate greater than or equal to x0. If there
are no points that satisfy these conditions, the query returns the special value null. (For
example, in Figure 2(b), the query returns point a.)
Hint: In all cases, it is possible to answer queries in O(log2 n) time. (Cascading, which
we mentioned but didn’t discuss in detail, should not be needed.)
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
