5. (a) In class we saw how to use an interval tree to store a set...

Transcribed Image Text:

5. (a) In class we saw how to use an interval tree to store a set of intervals. Our interval tree had a search operation allowing us to search for an interval overlapping a given interval. In this question we want to produce an algorithm that given an unordered list of n intervals, determines in O(n log n) worst case time, whether it contains a pair of intervals that overlap. Do not use an interval tree for this algorithm. (b) Justify why your algorithm is correct and runs in the required time. We now extrapolate our interval problem to a set of rectangles whose edges are parallel to the x and y axes. Suppose R and R2 are rectangles whose edges are parallel to the x and y axes. Define what it means for R and R2 to overlap in terms of their left and right a coordinates and top and bottom y coordinates. (c) Describe an algorithm that, given an unordered list of n rectangles whose edges are parallel to the x and y axes and which are specified by their left and right x coordinates and top and bottom y coordinates, decides, in O(n log n) worst case time, whether it contains a pair of rectangles that overlap. Justify why your algorithm is correct and runs in the required time. Hint: Make use of both your answer to (a) and the interval tree we learned in class. 5. (a) In class we saw how to use an interval tree to store a set of intervals. Our interval tree had a search operation allowing us to search for an interval overlapping a given interval. In this question we want to produce an algorithm that given an unordered list of n intervals, determines in O(n log n) worst case time, whether it contains a pair of intervals that overlap. Do not use an interval tree for this algorithm. (b) Justify why your algorithm is correct and runs in the required time. We now extrapolate our interval problem to a set of rectangles whose edges are parallel to the x and y axes. Suppose R and R2 are rectangles whose edges are parallel to the x and y axes. Define what it means for R and R2 to overlap in terms of their left and right a coordinates and top and bottom y coordinates. (c) Describe an algorithm that, given an unordered list of n rectangles whose edges are parallel to the x and y axes and which are specified by their left and right x coordinates and top and bottom y coordinates, decides, in O(n log n) worst case time, whether it contains a pair of rectangles that overlap. Justify why your algorithm is correct and runs in the required time. Hint: Make use of both your answer to (a) and the interval tree we learned in class.