[Solved]: 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 tramsitive, 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 quesion:

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

We have 2 cases:

1. $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 point that will dominate $p$.
2. $exists d in S, d is dominanting p$, then $p notin M$, because it will be more optimal include $d$ in $M$ and exlude $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$.

1. Include first point from $L$ in $M$ and remember this point as $T$.
2. 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)$.