minimum subset of dominating 2D points
$O(N^2)$ solution

First of all define dominant relation for points:


  Point $d(x_d, y_d)$ is dominating point $p(x_p, y_p)$ iff $x_p \le x_d$ and $y_p \le y_d$. Also easy to see that this relation is transitive, i.e. if $a$ dominating $b$ and $b$ dominating $c$, then $a$ dominating $c$.


Let $M$ be minimum(-size) dominating subset of set $S$. Now we need to check which point will be in $M$. Let answer on the question:


  Is $p \in S$ is $M$ or not?


We have 2 cases:


$\nexists d \in S, d$ is dominanting $p$, then $p \in M$, if we will not include $p$ in $M$ we will not be able to find a point that will dominate $p$.
$\exists d \in S, d$ is dominanting $p$, then $p \notin M$, because it will be more optimal include $d$ in $M$ and exclude $p$, as every point in $A$ that is dominated by $p$ is dominated by $d$ also, but $d$ is dominating at least one more point (itself).


First case make sure that $M$ will dominate $S$, second case that $M$ is minimal among all dominating subsets.

And now we have easy $O(N^2)$ solution: for each point $p \in S$ check membership in $M$; to do that we need to check that there is no point $d \in S$ that dominating $p$.



$O(N \log N)$ solution

To construct solution with $O(N \log N)$ time-complexity, let see some example of sets $S = \{A, B, C,..., N\}$ and $M = \{N, B, I, H\}$:


To find $M$ we need to sort points in $S$ by $x$ in descending order, and if $x's$ the same by $y$ in descending order (it can be done in $O(N \log N)$, let call this sorted list $L$.


Include first point from $L$ in $M$ and remember this point as $T$.
Iterates through $L$ (let $C$ current considered point from $L$):


if $C$ is dominated by $T$ than skip $C$ and go to next point in $L$;
else include $C$ in $M$ and set $T = C$
This step can be performed in $O(N)$.