You're right! They seem to have fixed a bug in their test program, and I'm now credited with solving that problem.

As for the justification, it shouldn't be too hard to show with a little algebra that

TaxicabDistance(x1+y1, y1-x1, x2+y2, y2-x2)/2 = ChebyshevDistance(x1, y1, x2, y2)

where

ChebyshevDistance(x1, y1, x2, y2) = max(|x1-x2|,|y1-y2|) and

TaxicabDistance(x1, y1, x2, y2) = |x1-x2|+|y1-y2|.

There's a nice justification in

http://news.ycombinator.com/item?id=2865396

So, we have a linear transformation from R^2 into R^2 with matrix

     1   1

     1  -1

So, the rows are orthogonal! And the columns! It's not quite an orthonormal matrix where its transpose is its inverse because the length of each row, column is not 1, but it's 'close' to orthonormal.

So, except for a scalar multiple, this linear transformation has to be an 'isometry', that is, preserves lengths and angles, lengths in the usual metric in R^2. So, this linear transformation starts to 'smell good'!

Looking, for the given metric, consider the 'unit circle', that is, all points distance 1 from the origin. Then consider the image of these points under this linear transformation. That 'circle' is a square with diagonal (1,1) to (-1,-1). Then its image is a 'diamond', that is, a square with diagonal, say, (-2,0) to (2,0). So, except for a scalar 2, we have preserved distances. That is, our linear transformation is 1-1 between a 'circle' in one metric and a circle in the other metric. That's close enough to a proof for gumment work!

Nice.

Be wise, generalize: So we have taken a nasty problem with an n^2 solution, or some tricky, solution iterating with convexity, and with a simple linear transformation turned the problem into a 'decomposition' on the two coordinates separately. So, where else can we take a challenging optimization problem, stuff a linear transformation inside the problem, and get a much simpler problem? Hmm ....