5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Sort the elements of S by the maximal entry of the vector, T by minimal entry (both in O(m log m) time for fixed d) and compare maximal element of T with minimal element of S? More spitballing than something I know to work, though. If I had to figure out whether it works, I'd try induction on d. $\endgroup$ – G. Bach Aug 26 '13 at 4:08
  • $\begingroup$ @G.Bach I think you may have misunderstood / misread the definition of the comparison. It's u_i ≤ v_i for all i, not u_i ≤ v_j for all i,j. Meaning you only compare one element with one element, as in (1,2,3) <= (2,3,4). $\endgroup$ – Dukeling Aug 26 '13 at 8:56
  • $\begingroup$ Generalizing the approach for $d= 1$, you could try finding all minimal and maximal elements (note the plural) of your sets and compare those pairwise. However, I don't know how complex finding these elements is in general (maybe there are methods to convert posets into a graph representation of their Hasse-diagrams and then find the sources / sinks), and whether the number of extremal elements in the $d$-fold product of a poset $P$ is nicely (something like $\Theta(d)$) related to the number of extremal elements in $P$ itself. $\endgroup$ – Cornelius Brand Aug 26 '13 at 9:53
  • 1
    $\begingroup$ @Raphael I assume you suggest a method similar to what I said in my comment. Then, how would you do that in $O(m)$ time (the width of the given poset may be in fact $m$)? $\endgroup$ – Cornelius Brand Aug 26 '13 at 13:59
  • 1
    $\begingroup$ @C.Brand True, $\Theta(m \cdot w)$ is the correct time if the width (size of a largest subset of incomparable vectors) is $w$ with the naive approach. Off the top of my head I don't know a faster algorithm. $\endgroup$ – Raphael Aug 26 '13 at 15:32
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Beautiful! Thank you. Based upon the Bentley paper you reference, it looks like when we have $d$ dimensions, this problem might be solvable in $O(n \lg^{d-1} n)$ time. That's pretty nifty. (Please check my reasoning. Have I understood the paper accurately, or did I go wrong somewher?) $\endgroup$ – D.W. Aug 29 '13 at 23:48
  • $\begingroup$ Yes, that's what I gathered as well. $\endgroup$ – Tom van der Zanden Aug 31 '13 at 20:32

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.