Comparing sets of vectors

Question

If $u,v \in \mathbb{R}^d$ are two $d$-dimensional vectors, say that $u\le v$ if $u_i \le v_i$ for all $i=1,\dots,d$. In other words, comparisons on vectors will be pointwise.

Let $S,T$ be two subsets of $\mathbb{N}^d$ of size $m$. Is there an efficient way to test whether there exists $s\in S, t \in T$ such that $s\le t$? The naive algorithm does $m^2$ comparisons between vectors; is there a more efficient algorithm?

If $d=1$, this is very easy: we simply find the smallest element in $S$ and the largest element in $T$, which can be done with $O(m)$ comparisons. But already when $d=2$, it seems much harder. Any ideas?

Answer 1

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&conquer strategy: if a pair of comparable elements exist, then either:

1. Both elements are contained in the first half of the list
2. Both elements are contained in the second half of the list
3. 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&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