Recovering the slope of a digitized line
The computational geometry approach would replace each pixel (i,j) with vertical segment (i, j+[-1/2,1/2]), take the convex hulls of the upper and lower sets of endpoints, and compute the inner common tangents -- these delimit the range of slopes that produce this digital line. This is just the geometric interpretation of the linear program that you mention in your slides.  O(n) time suffices for the LP by Meggiddo, or for the hulls and tangents by Graham-Yao.