The number of digital straight lines on an N*N grid

Abstract

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.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>