A point (x1, y1) is said to dominate another point (x2, y2) in the plane if both

Question

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. 3 This time, design a solution to this problem by applying the algorithm design paradigm of divide-and-conquer. Your algorithm must divide the point set S into two subsets according to x-coordinates, compute the maximal points of each subset recursively, and then, in the COMBINE step, compute the maximal points of the entire set.

Explanation / Answer

Input:
An array S[1..n] of pairs of integers (x, y) instead of the x- and y-coordinates of a set of points in the plane.
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.
Step 1:
Sort S[1..n] of pairs (x,y) in incresing order of x ....worst-case running time is (n lg n)
Step 2:
Sort the sorted output of step 1 of pairs (x,y) in increasing order of y using a stable sort such that if (x',y') appear before in output of step 1 than it also appear before output of step 2 ....worst-case running time is (n lg n)In output of step 2 is arrange in order of x and y both so just scanning the output of step 2This will have most terrible-case running time So most terrible-case operation time is (n lg n)+(n lg n)+ = (n lg n)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.