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})$.

  • 1
    $\begingroup$ "...from another angle." Nice. $\endgroup$ – 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.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.