minimum subset of dominating 2D points

From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ?

$M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) in M such that $x \le a$ and $y \le b$

Another related question: is any minimal set also minimum?

It is trivial to find a minimal set in $|S|^2$ time complexity.

$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)$.

StackExchange Computer Science Q#44670, answer score: 5