Comparing sets of vectors
In the case $d=2$, it is possible in $O(n \log n)$ time. First, sort the input elements on their first component. Then, use a recursive divide&amp;conquer strategy: if a pair of comparable elements exist, then either:


Both elements are contained in the first half of the list
Both elements are contained in the second half of the list
A pair can be formed by taking on element from the first half and one from the second half


Cases 1 and 2 can be solved by recursion. Case 3 can be solved by finding the element from the first half with the lowest second component and finding the element with the highest second component from the right list.

It is possible to implement the divide&amp;conquer strategy in $O(n)$ time so the time complexity is dominated by presorting the list, taking $O(n \log n)$ time.

When going to $d=3$, a similar strategy might be possible, but the third case is harder: given two sets of 2-dimensional vectors $A,B$ it requires finding $a\in A,b\in B$ such that $a\leq b$.

Edit: the following paper may be relevant, it computes for each vector how many vectors are ranked lower in less than quadratic time. http://www.cs.uiuc.edu/class/fa05/cs473ug/hw/p214-bentley.pdf