[psimons2]

You could also use SMAWK.

[gliese1337]

http://www.egr.unlv.edu/~larmore/Courses/CSC477/monge.pdf

How? That is an algorithm for a completely different problem, which is not obviously reducible to this one.