Counting the Number of Shortest Chamfer Paths in the Square Grid

Abstract

In this paper, the number of shortest paths between any point pairs of the square grid, based on weighted distances, is computed. We use two types of steps on the gridlines and diagonal steps. Consequently, we use an 8-adjacency square grid, that is, one where a first weight is associated with the horizontal and vertical movements, while a second weight (not necessarily different from the first) is assigned to the diagonal steps. The chamfer distance of two points depends on the numbers and weights of the steps in a 'shortest path'. In special cases, the cityblock and the chessboard distances, the two most basic and widely used digital distances (they are also referred as L1 and L. distances, respectively) of the two-dimensional digital space occur. Although our combinatorial result is theoretical, it is closely connected to applications, such as communication networks, path counting in digital images, traces and trajectories in 2D digital grids. We consider all seven cases with non-negative weights and also the case when negative weights are allowed.