The number of digital straight lines on an N*N grid
Jack Koplowitz, Michael Lindenbaum, Alfred Marcel Bruckstein · IEEE Transactions on Information Theory · 1990
The number of digital straight lines on an N*N grid is shown. A digital straight line is equivalent to a linear dichotomy of points on a square grid. The result is obtained by determining a way of counting the number of linearly separable dichotomies of points on the plane that are not necessarily in general position. The analysis is easily modified to provide a simple solution to a similar problem considered by C. Berenstein and D. Lavine (1988) on the number of digital straight lines from a fixed starting point.>