# How to compare n number of m-dimensional points among one another with minimum time complexity?

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 ?

• 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$? – D.W. Jan 24 '20 at 6:35
• 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. – ssarmah Jan 24 '20 at 6:46
• 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. – Aaron Rotenberg Jan 24 '20 at 15:32
• 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. – ssarmah Jan 24 '20 at 16:35

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.