$3.(30$ points$)$ Given two $2-$dimensional points A $=$x$1,$ y$1$ and B $=$x$2,$ y$2,$ we say that A $<$ B

if x$1<$ x$2$ and y$1<$ y$2.$ Given a set of S $=\{$A$1,$ A$2,,$ An$\}$ of $2-$dimensional points, the goal

is to output a maximal set S$$ S such that for every pair of points C and D in S$,$ neither

C $<$ D nor D $<$ C$.$ Give a divide and conquer algorithm to solve this problem. Write

the recurrence relation describing the runtime of the algorithm and give the solution to the

recurrence. You do not need to show your work for deriving the solution to the recurrence.

Your will receive zero credit if you do not use divide$-$and$-$conquer.

Note that a subset S$$ of S maximal if the following holds: For every D in S $$ S$,$ there exists

C in S$$ such that either C $<$ D or D $<$ C$.$

$2$