Number of words characterizing digital balls on the triangular tiling

Abstract

In this paper, digital balls on two regular tessellations of the plane, on the square and on the triangular grids are analyzed. The digital balls are defined by digital, i.e., path based distance functions. The paths (built by steps to neighbor pixels) from the center to the points (pixels) of the balls are described as traces and generalized traces, respectively, on these grids. On the square grid, there are two usual types of neighborhood, and thus, the number of linearizations of these traces is easily computed by a binomial coefficient. The number of linearizations gives the number of words that describe the same digital ball. In the triangular tiling there are three types of neighborhood, moreover, this grid is not a lattice, therefore, the possible paths that define a ball form a more complicated set, a kind of generalized trace. The linearizations of these traces are described by an associative rewriting system, and, as a main combinatorial result, the number of words that define the same ball is computed. © Springer International Publishing Switzerland 2016.