Maxima of diagonals in a column wise and row wise sorted matrix
Great question! "Distance Transforms of Sampled Functions", by Felzenszwalb and  Huttenlocher shows how to compute this in $O(n \lg n)$ time.

"Necklaces, Convolutions, and X+Y", By Bremner et al. shows a $O\left(\frac{n^2}{\frac{\lg^2 n}{(\lg \lg n)^3}}\right)$ algorithm for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in the nonuniform linear decision tree model.