Let S = {p1, . , pn} be a set of n points in the plane.

Let S = {p1, . . . , pn} be a set of n points in the plane. We say that a point pi ∈ S sees to the southwest if there are no points of S having both their x-coordinate strictly less than that of pi and their y-coordinate strictly less than that of pi (i.e., there are no points of S strictly to the "southwest" of pi). The southwest fence of S is the polygonal chain whose vertices are the points pi ∈ S of S that see to the southwest, given in order from left to right (i.e., increasing x-coordinate).

(a). Draw the set of points S = {(3, 2),(1, −1),(2, −1), 5, −2),(0, 3),(2, 2),(−1, 4)} and highlight (circle) those points that see to the southwest. Show also the southwest fence for S.

(b). Describe how to apply the divide and conquer method to give an algorithm to compute the southwest fence of a set S of n points in the plane. What is the efficiency of the algorithm, in big-Oh? (You do not need to write code or pseudocode for this problem, but try to describe the algorithm as clearly as you can, in reasonable length.)

(c). Optional theory question (for 1 bonus point): Give an argument that Ω(n log n) is a lower bound for computing and outputting the southwest fence of an (unordered) set of n points in the plane.

(d). Optional programming exercise (for 1 bonus point): Implement the divide-and-conquer algorithm, in a language of your choice. Show the code, and a screen shot of the output (graphical or text, or both) on an example.