Consider the following problem. You are given a set R of n rectangles, where each rectangle r e R has (0,0) as the lower-left corner. The upper-right corner has an integer x- and y-coordinate and each rectangle in R has a distinct upper-right corner. We say a point p = (x, y) stabs a rectangle if it lies inside the rectangle (including the borders). We develop a data structures where we can efficiently add and remove rectangles and for a given point can efficiently find a stabbed rectangle. We choose to store the rectangles in a red-black tree T by the x-coordinate of their right- upper corner. Moreover, we augment each node v in the red-black tree by the maximum y-coordinate of the upper-right corner of any rectangle in the subtree rooted at v. (a) [1 points] Prove that the augmentation can be maintained without affecting the asymp- totic runtimes when inserting or removing a rectangle from the tree. (b) [1 points) To understand how this augmentation may help us consider the following case. Assume that at the root r of T the rectangle with upper-right corner (6,11) is stored and that the query point p = (7,8) If p stabs a rectangle where in the RB-tree can this rectangle be stored? (c) [4 points) Describe an algorithm that given a query point q can find a stabbed rectangle in T in O(log n) time. You may assume such a rectangle exists. Also analyse the runtime of your algorithm and argue its correctness. Consider the following problem. You are given a set R of n rectangles, where each rectangle r e R has (0,0) as the lower-left corner. The upper-right corner has an integer x- and y-coordinate and each rectangle in R has a distinct upper-right corner. We say a point p = (x, y) stabs a rectangle if it lies inside the rectangle (including the borders). We develop a data structures where we can efficiently add and remove rectangles and for a given point can efficiently find a stabbed rectangle. We choose to store the rectangles in a red-black tree T by the x-coordinate of their right- upper corner. Moreover, we augment each node v in the red-black tree by the maximum y-coordinate of the upper-right corner of any rectangle in the subtree rooted at v. (a) [1 points] Prove that the augmentation can be maintained without affecting the asymp- totic runtimes when inserting or removing a rectangle from the tree. (b) [1 points) To understand how this augmentation may help us consider the following case. Assume that at the root r of T the rectangle with upper-right corner (6,11) is stored and that the query point p = (7,8) If p stabs a rectangle where in the RB-tree can this rectangle be stored? (c) [4 points) Describe an algorithm that given a query point q can find a stabbed rectangle in T in O(log n) time. You may assume such a rectangle exists. Also analyse the runtime of your algorithm and argue its correctness
