ON THE NUMBER OF SHORTEST PATHS BY NEIGHBORHOOD SEQUENCES ON THE SQUARE GRID

Abstract

In this paper we are addressing a counting problem of discrete mathematics, more precisely of digital geometry. In the Euclidean plane the shortest path between any two points is given by the straight line segment connecting the points. In discrete mathematics, the shortest path is usually not unique, e.g., in graphs there could be several shortest paths between two vertices. In this paper, a special infinite graph, the square grid, (i.e., the usual digital plane) is used. In digital geometry there are various digital, i.e., path based distance functions. A neighborhood sequence B gives the condition for each step of a B-path separately what type of neighborhood is used in that step. Therefore, the length and also the number of the shortest paths between two points depend not only on the respective positions (coordinate differences) of the points but also on the neighborhood sequence B. We give an algorithm and also closed formulae to compute the number of shortest B-paths.