3. [8 marks A point (x1, y/i) is said to dominate another point (x2, 1/2) in the

Question

3. [8 marks A point (x1, y/i) is said to dominate another point (x2, 1/2) 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 S2(nlgn) 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 algo- rithm 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

Given the array S[1...n] of pairs of integers (x, y), we can aaply any good sorting argorihm to sort th pairs by degreasing order of x. The warst time complexity of such sorting algorithm is big omega of (n lg n).

Now again sort the above sorted array using a stable sorting methom in big omega of (n lg n). in decreasing order of y.

From the above sorted array we can get all skyline point in S . In worst case this will take n operation.

So the total complexity n warst case will be big omega of (n lg n + n lg n +n). that 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.