Number of Words Characterizing Digital Balls on the Triangular Tiling

详细信息    查看全文

• 关键词：Digital distance ; Shortest paths ; Neighborhood sequences ; Non ; traditional grids ; Digital disks ; Combinatorics ; Traces ; Trajectories ; Generalized traces
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9647
• 期：1
• 页码：31-44
• 全文大小：1,398 KB
• 参考文献：1.Das, P.P., Chakrabarti, P.P., Chatterji, B.N.: Distance functions in digital geometry. Inf. Sci. 42, 113–136 (1987)MathSciNet CrossRef MATH
  2.Deutsch, E.S.: Thinning algorithms on rectangular, hexagonal and triangular arrays. Comm. ACM 15, 827–837 (1972)CrossRef
  3.Diekert, V., Rozenberg, G. (eds.): The Book of Traces. World Scientific, Singapore (1995)
  4.Herendi, T., Nagy, B.: Parallel Approach of Algorithms. Typotex, Budapest (2014)
  5.Farkas, J., Baják, S., Nagy, B.: Approximating the Euclidean circle in the square grid using neighbourhood sequences. Pure Math. Appl. 17, 309–322 (2006)MathSciNet MATH
  6.Janicki, R., Kleijn, J., Koutny, M., Mikulski, L.: Generalising traces, CS-TR-1436. Technical report, Newcastle University, Partly Presented at LATA 2015 (2014)
  7.Mateescu, A., Rozenberg, G., Salomaa, A.: Shuffle on trajectories: syntactic constraints. Theoret. Comput. Sci. 197, 1–56 (1998)MathSciNet CrossRef MATH
  8.Mazurkiewicz, A.W.: Trace Theory: Advances in Petri Nets 1986. LNCS, vol. 255, pp. 279–324. Springer, Heidelberg (1987)
  9.Nagy, B.: Finding shortest path with neighborhood sequences in triangular grids. In: 2nd IEEE R8-EURASIP International Symposium ISPA, Pula, Croatia, pp. 55–60 (2001)
  10.Nagy, B.: Metrics based on neighbourhood sequences in triangular grids. Pure Math. Appl. 13, 259–274 (2002)MathSciNet MATH
  11.Nagy, B.: Shortest path in triangular grids with neighbourhood sequences. J. Comput. Inf. Technol. 11, 111–122 (2003)
  12.Nagy, B.: Distance functions based on neighbourhood sequences. Publicationes Math. Debrecen 63, 483–493 (2003)MathSciNet MATH
  13.Nagy, B.: Characterization of digital circles in triangular grid. Pattern Recogn. Lett. 25, 1231–1242 (2004)CrossRef
  14.Nagy, B.: Metric and non-metric distances on \(\mathbb{Z}^n\) by generalized neighbourhood sequences. In: 4th ISPA: International Symposium on Image and Signal Processing and Analysis, Zagreb, Croatia, pp. 215–220 (2005)
  15.Nagy, B.: Distances with neighbourhood sequences in cubic and triangular grids. Pattern Recogn. Lett. 28, 99–109 (2007)CrossRef
  16.Nagy, B.: Distance with generalized neighbourhood sequences in \(n\) D and \(\infty \) D. Discrete Appl. Math. 156, 2344–2351 (2008)MathSciNet CrossRef MATH
  17.Nagy, B., Strand, R.: Approximating Euclidean circles by neighbourhood sequences in a hexagonal grid. Theoret. Comput. Sci. 412, 1364–1377 (2011)MathSciNet CrossRef MATH
  18.Rosenfeld, A., Pfaltz, J.L.: Sequential operations in digital picture processing. J. ACM 13, 471–494 (1966)CrossRef MATH
  19.Rosenfeld, A., Pfaltz, J.L.: Distance functions on digital pictures. Pattern Recogn. 1, 33–61 (1968)MathSciNet CrossRef
  20.Stojmenovic, I.: Honeycomb networks: topological properties and communication algorithms. IEEE Trans. Parallel Distrib. Syst. 8, 1036–1042 (1997)CrossRef
  21.Yamashita, M., Honda, N.: Distance functions defined by variable neighborhood sequences. Pattern Recogn. 17, 509–513 (1984)MathSciNet CrossRef MATH
  
• 作者单位：Benedek Nagy (16) (17)
  
  16. Department of Computer Science, Faculty of Informatics, University of Debrecen, Debrecen, Hungary
  17. Department of Mathematics, Faculty of Arts and Sciences, Eastern Mediterranean University, Famagusta, North Cyprus, Turkey
  
• 丛书名：Discrete Geometry for Computer Imagery
• ISBN：978-3-319-32360-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

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.