# inferring the slope of a digitized line

Given real numbers $a$ and $b$, and an integer $n \geq 2$, let $f(n,a,b)$ be the minimum of $(nint(ja+b)-nint(ia+b)+1)/(j-i)$ (for $1 \leq i < j \leq n$) minus the maximum of $(nint(ja+b)-nint(ia+b)-1)/(j-i)$ (for $1 \leq i < j \leq n$), where $nint$ is the nearest integer function. What is known about the rate at which $f(n,a,b)$ goes to 0 as $n$ goes to infinity, for "generic" real numbers $a, b$? (That is, real numbers whose continued fractions have convergents that grow as dictated by Khinchin's law.) Experiments suggest that $f(n,a,b) = O(1/n^2)$.

This is related to the question of how accurately one can infer the slope of a line from a digitized version of the line; if there is any literature on this question, I would be very interested in pointers.

I am also interested in knowing how one can most efficiently compute the minimum of $(nint(ja+b)-nint(ia+b)+1)/(j-i)$ (for $1 \leq i < j \leq n$) and the maximum of $(nint(ja+b)-nint(ia+b)-1)/(j-i)$ (for $1 \leq i < j \leq n$).

For context, I'll mention that several recent postings of mine (especially sums of fractional parts of linear functions of n) approach this question from another angle. Specifically, my posting from last week is related to an estimator of the slope of the line that can be computed in linear (as opposed to quadratic) time but has typical error $O(1/n^{3/2})$.

-
"...from another angle." Nice. – Allen Knutson Feb 15 '11 at 19:26

Not an answer, more like an overgrown comment. The nearest integer to $x$ is the floor of $x+(1/2)$, and you can incorporate the 1/2 into $b$, so you're talking about things like $([ja+b]-[ia+b]+1)/(j-i)$. Now floor is identity minus fractional part, so we get to $(ja+b-\lbrace ja+b\rbrace-ia-b+\lbrace ia+b\rbrace+1)/(j-i)$, which simplifies to $a+(\lbrace ia+b\rbrace-\lbrace ja+b\rbrace+1)/(j-i)$. So you're looking at the minimum of $(\lbrace ia+b\rbrace-\lbrace ja+b\rbrace+1)/(j-i)$ minus the maximum of $(\lbrace ia+b\rbrace-\lbrace ja+b\rbrace-1)/(j-i)$, which may be a little more tractable than what you started out with.