Recovering the slope of a digitized line Has there been any work on recovering the slope of a line segment from its digitization?
One can't do this with perfect accuracy, of course; what one wants is a method of deriving from a digitized line an interval of possible slopes.

(The notion of a digitized line that I am using is Rosenfeld's: the set of pairs $(i,nint(ai+b))$ where $i$ ranges over the integers (or a block of consecutive integers) and $nint(x)$ denotes the integer nearest to $x$ (if $x=k+1/2$, we take $nint(x)=k$).)

I've done some work on this on my own (see http://jamespropp.org/SeeSlope.nb) but I have
no formal background in computational geometry so I suspect I may be reinventing the wheel, since the question seems like such a basic one.

In fact, I know that the linear regression method of estimating the slope is in the 
literature, but I haven't been able to find my $O(1/n^{1.5})$ result anywhere.  (This
result says that if one chooses $a$ and $b$ uniformly at random in $[0,1]$, then the 
difference between the slope $a$ of the line $y=ax+b$ and the slope $\overline{a}$ of
the regression line approximating the $n$ points $(i,nint(ai+b))$ ($1 \leq i \leq n$) 
has standard deviation $O(1/n^{1.5})$.)

Any leads or pointers to relevant literature will be greatly appreciated.

Jim Propp (JamesPropp@ignorethis.gmail.com)
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.