Question

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 http://mathoverflow.net/questions/54731/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})$.

Answer 1

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.

EDIT: As to whether someone has already done this, the paper by Melter, Stojmenovic, and Zunic, A new characterization of digital lines by least square fits, Pattern Recognition Letters 14 (1993) 83-88, available at http://www.site.uottawa.ca/~ivan/F29-digital-line-lsf.PDF may be relevant or may point you to some useful work.

FURTHER EDIT: Another paper that looks like it might be useful is MR2323394 (2008e:68149) Uscka-Wehlou, Hanna, Digital lines with irrational slopes, Theoret. Comput. Sci. 377 (2007), no. 1-3, 157–169.