Question 5. (30 points) 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 yi denote the x 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 x; + x; and y; # y;). Point pi is said to be dominant if no other point p; of S has both x; > x; and y; > 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 li, 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. Question 5. (30 points) 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 yi denote the x 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 x; + x; and y; # y;). Point pi is said to be dominant if no other point p; of S has both x; > x; and y; > 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 li, 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
