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 haveno 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.  (Thisresult 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}$ ofthe 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)
Recovering the slope of a digitized line
reference request;cg.comp geom;cv.computer vision;image processing
See Random Generation of Finite Sturmian Words by Berstel and Pocchiola for a proof that the feasible region of your LP has only three or four sides, as well as a simple algorithm for finding the polygon given slope and intercept.  (They are dealing with recognizing Sturmian Words, but the problems are strongly related.)They also give an explicit enumeration of the polygons, so it may be possible to enumerate the areas of the polygons and the ranges of the slopes, so you may be able to get the expected value of the range of slopes (as well as higher moments)  as an explicit sum.