2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ This problem is also known as "pareto front". $\endgroup$ – Tom van der Zanden Jul 23 '15 at 13:52
4
$\begingroup$

$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:

  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 a 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 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\}$: answer

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)$.
$\endgroup$
2
$\begingroup$

Yes. There is a divide-and-conquer algorithm whose running time is $O(n \log n)$. For an overview of the algorithm, see the following research paper:

A Calculator for Pareto Points. Marc Geilen and Twan Basten. Design, Automation & Test in Europe Conference & Exhibition 2007 (DATE'07), IEEE.

I believe the divide-and-conquer algorithm is initially due to Bentley and Kung.

See also the skyline problem, which is essentially the same problem in different terms: What are some interesting applications of the skyline problem?

$\endgroup$
1
$\begingroup$

Viewing $S$ as a partially ordered set, your question is equivalent to finding all maximal elements in $S$.

In fact, a dominating subset must contain all maximal elements, and the subset of all maximal elements is clearly a dominating subset.

Thus there is only one minimal dominating subset $M$, namely the set of all maximal elements in $S$, and the answer to your "another related question" is "yes".

There is an algorithm that finds $M$ in $O(N log(N))$ time, where $N = |S|$.

First sort the points according to $x$ coordinates (for points with same $x$ coordinates, sort according to $y$). Then, go through all the points from bigger $x$ to smaller $x$, add a point to $M$ if and only if its $y$ coordinate is strictly bigger than any $y$ coordinate you've seen before it.

This should be good enough in most applications.

$\endgroup$
  • $\begingroup$ i think there is an error in this part "add a point to M if and only if its y coordinate is strictly bigger than any y coordinate you've seen before it". check the accepted solution $\endgroup$ – Issam T. Jul 24 '15 at 10:13
  • 1
    $\begingroup$ @Issam T. I really can't figure out what's wrong about my answer. Note that I mentioned "for points with same x coordinates, sort according to y". I think the accepted answer just did the same as I do, except that he added pictures to illustrate. Well anyway that's your question... $\endgroup$ – WhatsUp Jul 24 '15 at 11:15
  • $\begingroup$ ok I read again. and the problem is in "add a point to M if and only if its y coordinate is strictly bigger than any y coordinate you've seen before it". it should be either "add a point to M if and only if its y coordinate is strictly bigger than all y coordinates you've seen before it" or "add a point to M if and only if its y coordinate is strictly bigger than the last y coordinate you've seen before it". It is probable though that this is what you had in mind and that only english failed you. Thanks for your help anyway +1 $\endgroup$ – Issam T. Jul 24 '15 at 16:20
  • $\begingroup$ @Issam T. Aha I get it now... $\endgroup$ – WhatsUp Jul 24 '15 at 16:40
-1
$\begingroup$

I have built a new algorithm to find the minimal set M but I can't check whether the algorithm is correct or not. The algorithm is as follows: 1. Consider the new array formed by multiplying the abssica array and the corresponding ordinate array and arrange it in ascending order. Next we arrange the abssica array and the ordinate array according to the new array formed. 2. Next we define the quantity:(diff of abssica)*(diff of ordinate)=m. We initialize m=0 and also min=m. 3. Next we include the last elements of the new abssica and ordinate array formed by the arranging the original ones in M. 4. Now we check m for the second last point of the new abssica and ordinate array and if mmin we leave this point and check the third last point and this goes on till the new abssica and ordinate arrays get exhausted. Just tell me about the correctness of the algorithm. There is no need to worry about time complexity. Its O(nlgn).

$\endgroup$
  • $\begingroup$ It looks like a separate question, not a full answer. $\endgroup$ – Evil Aug 17 at 12:32
  • $\begingroup$ No it's not like that I have checked for some cases and the answer matches but I can't prove for general cases $\endgroup$ – Vinayak Dutta Aug 18 at 13:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.