3. [8 marks] A point (x1, y1) is said to dominate another point (x2, y2) in the plane if both x1 x2 and y1 y2 hold. For example, (5, 2) dominates (3, 1) and (5, 1), but neither of the two points (3, 2) or (2, 5) dominates the other. A point p is a skyline point of a point set S if there does not exist another point in S that dominates p. The problem of computing the skyline of a given point set, is to report, from left to right, all the skyline points in a given point set. Prove that the worst-case running time of any algorithm for the above problem is (n lg n) under the comparison-based model. In this model you are allowed to do comparisons and arithmetic operations involving the inputs, and the running time is measured by the number of comparisons performed. To prove this, you can use the known fact that the worst-case running time of any algorithm for sorting an array of n distinct integers is (n lg n) under the same model. You can also assume that the coordinates are integers. You can make the following assumptions about the input and the output of any algorithm that solves the problem of computing skylines: Input: An array S[1..n] of pairs of integers (x, y) representing the x- and y-coordinates of a set of points in the plane. You can assume that there are no duplicate points in S. Output: An array M of pairs of integers such that its elements M[1], M[2], . . . give the coordinates of all the skyline points in S, listed from left to right. Note: You are NOT asked to give an algorithmic solution to the above problem. Instead, you are asked to prove a lower bound on the worst-case running time of any algorithm that solves this problem