Suppose you are given a set S of n two-dimensional points P1, P2, ..., Pn in...

   

Transcribed Image Text:

Suppose you are given a set S of n two-dimensional points P1, P2, ..., Pn in an arbitrary order (i.e., neither x-sorted nor y-sorted). Let x, and y, denote ther and (respectively) y coordinate of point p₁, and assume that all coordinates are positive. No two points of S have same x coordinate, or the same y coordinate (i.e., i j implies tij and yi y₁). Point p; is said to be dominant if no other point p; of S has both ; > x; and yj > yi. Let Dom (S) be the subset of S that contains only its dominant points. For example, if S consists of the 5 points (3, 5), (2,3), (4,4), (6, 1), (1,2) then Dom (S) would consist of points (3,5), (4,4), (6, 1) 1. Explain how, given S as input, Dom(S) can be computed with a single run of the skyline algorithm described in slide set 4. Make sure you explain what input is given to the skyline algorithm (what are the buildings?) and how its output is used to obtain Dom(S). Note that the skyline algorithm does not require that buildings have distinct l, or distinct ri, or distinct hi. Give a brief proof of correctness of your solution. Note. You do not need to modify the internals of the skyline algorithm, it is enough to provide it with a judiciously chosen input, and to make use of the corresponding output. 2. Explain how, if S was given in x-sorted order, a single scan of S can be used to produce Dom (S) in O(n) time. Give a brief proof of correctness of your solution. Suppose you are given a set S of n two-dimensional points P1, P2, ..., Pn in an arbitrary order (i.e., neither x-sorted nor y-sorted). Let x, and y, denote ther and (respectively) y coordinate of point p₁, and assume that all coordinates are positive. No two points of S have same x coordinate, or the same y coordinate (i.e., i j implies tij and yi y₁). Point p; is said to be dominant if no other point p; of S has both ; > x; and yj > yi. Let Dom (S) be the subset of S that contains only its dominant points. For example, if S consists of the 5 points (3, 5), (2,3), (4,4), (6, 1), (1,2) then Dom (S) would consist of points (3,5), (4,4), (6, 1) 1. Explain how, given S as input, Dom(S) can be computed with a single run of the skyline algorithm described in slide set 4. Make sure you explain what input is given to the skyline algorithm (what are the buildings?) and how its output is used to obtain Dom(S). Note that the skyline algorithm does not require that buildings have distinct l, or distinct ri, or distinct hi. Give a brief proof of correctness of your solution. Note. You do not need to modify the internals of the skyline algorithm, it is enough to provide it with a judiciously chosen input, and to make use of the corresponding output. 2. Explain how, if S was given in x-sorted order, a single scan of S can be used to produce Dom (S) in O(n) time. Give a brief proof of correctness of your solution.

Answer rating: 100% (QA)

SOLUTION 1 Solution using the skyline algorithm Given a set S of n twodimensional points in arbitrary order we can use the skyline algorithm to find the dominant points in On time The idea is to treat ... View the full answer