Let R be a set of n rectangles, R_i = [l_i, r_i] ×[b_i, t_i], in the plane, with sides parallel to the coordinate axes. Let P be a set of n points, p_j = (x_j , y_j ), in the plane. For simplicity, assume that all x-coordinates and all y-coordinates in R∪P are distinct. Given R and P, our goal is to decide for every point in P whether or not that point lies inside at least one rectangle of R, i.e., the output should simply be “IN” if the point lies inside at least one rectangle of R, and “OUT” otherwise. (An example of this is when trying to classify the location of different mouse clicks on a computer screen that has multiple open windows.) We would like to design an O(n log n)-time sweepline algorithm for this problem which uses an interval tree as a supporting data structure. (Do not modify the tree; use it as a black-box and make calls to the relevant routines.)

DO: (a) Provide a discussion of the main ideas underlying your solution, from which the correctness of your approach is clear.
(b) Give pseudocode.
(c) Analyze the running time.

Answer rating: 100% (QA)

My solution involves constructing a support interval tree which allows us to quickly determine wheth... View the full answer