Number of words characterizing digital balls on the triangular tiling - Nagy, Benedek (Springer Verlag service@springer.de, 2016)
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.
19th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI 2016 -- 2016-04-18 through 2016-04-20 -- Nantes -- 173609
Keywords: Combinatorics; Digital disks; Digital distance; Generalized traces; Neighborhood sequences; Non-traditional grids; Shortest paths; Traces; Trajectories