Given two 2-dimensional points A = hx1, y1i and B = hx2, y2i, we say that A < B if x1 < x2 and y1 < y2. Given a set of S = {A1, A2, , An} of 2-dimensional points, the goal is to output a maximal set S 0 ? S such that for every pair of points C and D in S 0 , neither C < D nor D < C. Give a divide and conquer algorithm to solve this problem. Write the recurrence relation for the run-time and solve the recurrence. Your grade depends on the run-time. Your will receive zero credit, if you do not use divide-and-conquer. A subset S 0 of S maximal if the following holds: For every D ? S ? S 0 , there exists C in S 0 such that either C < D or D < C.

Please leave the psaudo code as possible, thanks.