Please help me with complete solution!!! And I will rise another 3000 points for
ID: 3564852 • Letter: P
Question
Please help me with complete solution!!!
And I will rise another 3000 points for the best solution!!!!
A point (xl: y1) is said to dominate another point (x2, y2) in the plane if both X1 ge X2 and y1 ge 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 ohm (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 ohm (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[l..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.Explanation / Answer
Sort all the lines on the value of ai (which is the slope)
The first and last items will definitely be included.
Make a list to put all the visible lines in, and add the first two lines to it (we might remove the second one, but the first one is there to stay). For each successive line yi, consider the x coordinate of its intersection with yi-2 and the x coordinate of the intersection of yi-1 and yi-2. While there is at least two items in the visible list and the x coordinate of the intersection of yi with yi-2 is less than the x coordinate of the intersection of yi-1 and yi-2, remove the last item from the visible list. After you're done removing stuff, add the current line to the visible list.
The first step of sorting is obviously something that can be done in O(nlogn) time.
The second step looks O(n2) at first, but it's actually O(n). The proof that it's O(n) is similar to that of the Graham Scan algorithm for finding a convex hull (which is also O(nlogn) only because there's a sorting step). The reason is that at every O(1) step, we either add a line to the list or remove a line from the list, and we never add and remove the same line from the list more than once.
so the time complexity overall is O(n log n)