Quadratic lower bound

Question

Consider three arrays $A,B,C$ of size $N$ consisting of integers. I want to verify the following constraint: for any two indices $0 \leq i,j < N$, $A[i] < A[j] \land B[i] < B[j] \implies C[i] < C[j]$. The trivial algorithm here does the verification in $O(N^2)$ time. Is there a sub-quadratic algorithm for this problem? Any insight on proving a super linear lower bound or a (near) linear time algorithm would be greatly appreciated.

Answer 1

One can also find an $O(n \log n)$ time algorithm in Jon Bentley, "Multidimensional Divide and Conquer", Communications of the ACM, April 1980.

Answer 2

I think this works, but I don't have time to check the details carefully right now. I'll sketch the ideas and finish later, or someone else can check.

Lemma 1. There is an $O(n\log n)$-time algorithm for the problem.

Proof sketch. The problem reduces (by sorting w.r.t. $A$ and negating $C$) in $O(n \log n)$-time to the following:

Given a sequence $(b_1, c_1), (b_2, c_2), \ldots, (b_n, c_n)$ of points in the plane (with integer coordinates), is there a point $(b_j, c_j)$ that dominates some earlier point $(b_i, c_i)$ (that is, an $i<j$ with $(b_i, c_i) < (b_j, c_j)$, coordinate-wise)?

The algorithm considers the points $(b_j, c_j)$ in the order given, and checks each to see whether it dominates some previously considered $(b_i, c_i)$. As soon as it finds such a dominator, it stops and returns 'yes'. If it never finds one, it returns 'no'

Suppose that the algorithm is considering a point $(b_j, c_j)$, and has not yet terminated, so none of the previous points are dominators. First consider the case that, among all of the previous points, none dominates another. Then the points can be ordered naturally, by increasing $b_i$ and decreasing $c_i$ simultaneously. The algorithm will maintain the previous points in, say, a balanced binary search tree, ordered accordingly. When the next point $(b_j, c_j)$ is considered, by searching in this search tree, in $O(\log n)$ time, the algorithm can determine whether there is a previous point that is dominated by $(b_j, c_j)$.

If there is, the algorithm halts and returns 'yes'. Otherwise, the algorithm inserts $(b_j, c_j)$ in the appropriate place in the order and continues.

To finish we deal with the possibility that $(b_j, c_j)$ might be dominated by some previous point or points $(b_i, c_i)$, as follows. We can find all such points in time $O(\log n)$ per point, and simply remove them, because any future point that dominates such a point $(b_i, c_i)$ will also dominate $(b_j, c_j)$ (which we retain). $~~~\Box$ ?