Chan's technique

Yesterday Timothy Chan sent me email about the complexity of min-plus convolution, at least partially laying the question to rest. Timothy's results rely on what is now commonly (if only informally) known in the computational geometry community as “Chan's technique”:

1. Read the literature.
2. Understand it.
3. Apply it correctly.

A summary of Timothy's email would be longer than the email itself, so I'll just quote it in full (with some mild formatting).

Hi Jeff,

I have two quick observations about the min-plus convolution problem you posed at the CCCG problem session (given real vectors A and B, compute C[k] = min_i=1..k A[i]+B[k-i]).

1. The problem can be solved in about n^3/2 comparisons, in a nonuniform (decision tree) model, by adapting an idea of Fredman ('76) that was originally used for all-pairs shortest paths (or more specifically, min-plus matrix multiplication).

Proof: First sort all differences of the form A[i]-A[i'] with |i-i'|≤d and B[j]-B[j'] with |j-j'|≤d; this takes O(dn log n) time. Because A[i]+B[k-i] < A[i']+B[k-i'] iff A[i]-A[i'] < B[k-i']-B[k-i], we can compute min_i=l..l+d A[i]+B[k-i] for any l without any new comparisons. So we can compute each C[k] by taking min over just O(n/d) terms. The total cost is O(dn log n + n²/d). Set d = sqrt{n/log n}. Q.E.D.

2. The problem can be solved in O(n²/log n) time, in the standard real RAM model, by using an idea from my WADS'05 paper on min-plus matrix multiplication.

Proof: Compute all dominating pairs between the two point sets in R^2d:

{p_i := (A[i]-A[i-d], A[i]-A[i-d+1], ..., A[i]-A[i+d]) | all i} and
{q_j := (B[j+d]-B[j], B[j+d-1]-B[j], ..., B[j-d]-B[j]) | all j}.

For each dominating pair (p_i,q_{k-i}), we know that A[i]+B[k-i] = min_{i'=i-d..i+d} A[i']+B[k-i']. So there are at most O(n^2/d) dominating pairs in total, and they can be found in total time O(2^O(d) n^1+ε + n²/d) (see my paper). Afterwards, we can compute each C[k] by taking min over just O(n/d) terms. Set d = delta log n for a small delta. Q.E.D.

I hope all this make sense. If so, the observations would suggest that n² is not a lower bound, but getting a substantially subquadratic-time algorithm could be difficult (like getting a truly subcubic algorithm for min-plus matrix multiplication)...

- Timothy

I really like Timothy's O(n²/log n)-time algorithm, especially because it doesn't save the log factor by playing funny games with bits; it's all done with real arithmetic. (Someone could probably get rid of another factor of O(log n / log log n) using the right bit-games, but that someone won't be me. I don't like bits.)

It's worth emphasizing that both of these algorithms can be described by families of 4-linear decision trees. This means that there is no hope of directly generalizing my lower bound techniques for 3SUM to the 4-linear decision tree model. Fredman's simple algorithm solves defeats my adversary in O(n3/2) time. (The log factor in Timothy's analysis can be removed using a different result of Fredman.) My lower bounds—and all the related results by Fredman, Dietzfelbinger, and Ailon and Chazelle—argue that it's hard to determine if a point in a high-dimensional polytope is on that polytope's boundary. Generalizing the 3SUM lower bound will require a more global argument about the entire n-dimensional hyperplane arrangement, if it can be done at all.

On the other hand, this raises two obvious questions. First, can the log factor be stripped from the complexity of other "min-convolution-hard" problems, or even 3SUM? Second, does Fredman's technique limit lower bound arguments for more general linear degeneracy problems?

An apology to my human readers: Sorry about the technical stuff. Here, enjoy some kittens.

Comments

[D. Eppstein]

I guess I must not be one of your human readers, because I think this stuff is fascinating. You can also immediately get a subquadratic algorithm from the decision tree result, by building a decision tree for a small enough problem and applying it separately to submatrices of the original nxn matrix of differences, but that seems to only save a log^{1/4}n factor compared to the full log in Timothy's approach.

On the other hand, I enjoy funny games with bits, so now I'm going to have to look at Erik's paper.