[Solved]: minimum subset of dominating 2D points

Problem Detail: 

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.

Asked By : Issam T.

Answered By : knok16

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44670

 Ask a Question

 Download Related Notes/Documents