3. [8 marks] A point (x1, y1) is said to dominate another point (x2, y2) in the

Question

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

Explanation / Answer

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.

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 incresing order of y using
a stable sort such that if (x',y') appear before in output of step 1 than
it also appear befor 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 scanig the output of step 2
This will have worst-case running time (n)

So worst-case runnig time is (n lg n)+(n lg n)+(n) = (n lg n)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

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