1. (40 points) Let P={p1,,pn} be a set of n points in the plane (R2), and let pi=(xi,yi) for each i. The Pareto set Pareto (P)P is the subset of P containing each point pi such that there exists no point pjP with i=j such that both xjxi and yjyi. In other words, each point of Pareto (P) has no other point of P both above and to the right of it; you can visualize them as the turns on a staircase. See Figure 1. 1 (P) Figure 1. The set Pareto (P). (a) Describe and analyze an O(nlogn) time algorithm to compute/output Pareto (P). [Hint: Write a modification of Graham's scan.] (b) Let h=Pareto(P). Describe and analyze an O(nh) time algorithm to compute/output Pareto (P). [Hint: Write a modification of Jarvis's march.] (c) Describe and analyze an O(nlogh) time algorithm to compute/output Pareto (P). For simplicity, you may assume that the value h is known in advance. [Hint: Write a modification of Chan's convex hull algorithm.]