Question 5. (10 points) Sweeping the plane Given a set of points {(x,y)} 1 ? R2 give an algorithm to find the number of points in the lower left quadrant of each point, in O(nlog n). E.g. for the following set of points: Figure 1: Plot of input points 4 4 The algorithm should have the following output: Note 5.1. Assume that the points are given in left to right ordering. Hint 5.1. Use an AVL tree to store the points (what ordering is there on the points?). Show how we can use this to find the number of points below each point. What augmentations do we need the tree to have if we want both left and below