2
$\begingroup$

Suppose there are four points (n = 4) which are four dimensional (m = 4) . Lets say these points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4). What is the best data structure to compare all points among one another based on their values in corresponding dimensions ? Aim is to have minimum time complexity . (Practically n >> m ). The mentioned comparison is carried out to check whether points are mutually non-dominated or not. Example :

  1. A(4,1) and B(5,6) -> B dominates A since (5>4) and (6>1) . Therefore, A and B are not mutually non-dominated.
  2. C(4,1) and D(2,3) -> D doesn't dominate C ,since (3>1) but (2<4) . Similarly C also doesn't dominate D ,since (4>2) but (1<3) . Therefore, C and D are mutually non-dominated.

(Note : In general, if (X>=Y) -> X dominates Y )

Goal is to check for non-dominance among all possible combinations of points from the given set of points with minimum time complexity . With four points A, B, C, D possible combinations are AB, AC, AD, BC, BD, CD . If ALL of these six combinations are mutually non-dominated , then it can be concluded that given set of points are mutually non-dominated, else dominated.

Input : Set of points, Task : Check for non-dominance among all possible combination of points from the given set of points , Output : If ALL combinations are mutually non-dominated , print ('set of points are mutually non-dominated') . Else print ('set of points are not mutually non-dominated') .

I have taken a 2-D array for this purpose . For n points which are m-dimensional , I have used a (n * m) matrix and compared each row with every other row to check for non-dominance among rows. Suppose if points are : A(4,1,1,1) , B(3,2,1,1) , C(2,3,3,3) , D(1,4,4,4) , then matrix is : x[4][4] = { {4,1,1,1}, {3,2,1,1}, {2,3,3,3}, {1,4,4,4} } . Here the time complexity is : O(m * n * n).

(Note :In this method , each row of matrix is representing one point )

Is there any better approach which results lesser time complexity ?

$\endgroup$
  • 1
    $\begingroup$ Can you solve the question in 2 dimensions? in 3 dimensions? What's the best algorithm you have so far? Do you want an algorithm that works for all $m$, or only $m=4$? $\endgroup$ – D.W. Jan 24 at 6:35
  • $\begingroup$ It should work for any values of m and n (n >> m) .To make the question understandable , I have taken values as m = 4 and n = 4 as part of example. $\endgroup$ – ssarmah Jan 24 at 6:46
  • 1
    $\begingroup$ Thank you for your edits so far to this question, @ssarmah! You have clarified many points. One more question: would you consider (2, 1) to dominate (1, 1)? The current wording with $>$ instead of $\ge$ suggests that the answer is no, and therefore the set of those two elements is mutually non-dominated. I just want to make sure this is what you intended. $\endgroup$ – Aaron Rotenberg Jan 24 at 15:32
  • $\begingroup$ Welcome. In this example (2,1) dominates (1,1). Hence these set of points are not mutually non-dominated . '=' sign should be considered too. Now I have clarified this point too in the question. $\endgroup$ – ssarmah Jan 24 at 16:35
1
$\begingroup$

So you suggested the basic technique of checking all pairs which is $O(mn^2)$. Here are some things you can try first, at lower complexity, before falling back to an approach with a similar worst-case bound but likely better constants.

We represent each point $p_i = (x^i_1, \dots, x^i_m)$.

Then clearly there is a dominated pair if $\min_i \max_j x^i_j \leq \max_i \min_j x^i_j$. The time to evaluate this is $O(mn)$.

Next, we sort the points $m$ times, by each dimension. Let $r^i_j$ and $R^i_j$ be the indexes at which $p_i$ appears in each list (in range $[0,n)$), where the $r$ values have tie-breaks resolved down and $R$ values have tie-breaks resolved up, respectively. In other words, considering the values $3, 5, 5, 6$. Then the $r$ and $R$ values for the two points having $5$ would be $1$ and $2$. The time to evaluate this is $O(mn \log n)$, before we check conditions.

If $\min_i \max_j R^i_j \leq \max_i \min_j r^i_j$, then there is a dominated pair. The additional time to evaluate this is $O(mn)$ leaving the total time as $O(mn \log n)$.

Next, let $w_i = \sum_j r^i_j$ and $W_i = m(n-1) - \sum R^i_j$. Note that $w_i$ is an upper bound on the number of points that can't dominate $p_i$. Similarly, $W_i$ is an upper bound on the number of points that $p_i$ can't dominate. Thus, if $\min_i w_i < n - 1$ or $\min_i W_i < n - 1$, then there must be a dominated pair. The additional time to evaluate this is $O(mn)$ leaving the total time as $O(mn \log n)$.

Finally, as a fallback, for each point $p_i$ we know there are at most $\min_j R^i_j$ points which $p_i$ can dominate. Thus, knowing which list each $p_i$ obtained its minimum $R^i_j$ can give us a shorter list of points to check. The time here is still $O(mn^2)$ in the worst case, but the constant will be better than all pairs.

| cite | improve this answer | |
$\endgroup$

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.