Interactions between digital geometry and combinatorics on words

DOI10.4204/EPTCS.63.1MaRDI QIDQ2789507zbMATH OpenOpenAlexFDO

Authors Srečko Brlek

Publication date 1 March 2016

Published in Electronic Proceedings in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.3615, http://www.emis.de/proceedings/Words2011/paper.html?WORDS2011.1

Mathematics Subject Classification ID

Combinatorics on words (68R15) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We review some recent results in digital geometry obtained by using a combinatorics on words approach to discrete geometry. Motivated on the one hand by the well-known theory of Sturmian words which model conveniently discrete lines in the plane, and on the other hand by the development of digital geometry, this study reveals strong links between the two fields. Discrete figures are identified with polyominoes encoded by words. The combinatorial tools lead to elegant descriptions of geometrical features and efficient algorithms. Among these, radix-trees are useful for efficiently detecting path intersection, Lyndon and Christoffel words appear as the main tools for describing digital convexity; equations on words allow to better understand tilings by translations.

Recommendations

• Combinatorial View of Digital Convexity
• Lyndon + Christoffel = digitally convex
• First steps in the algorithmic reconstruction of digital convex sets
• Digital geometry
• scientific article; zbMATH DE number 2084493

Cited in

(12)

• First steps in the algorithmic reconstruction of digital convex sets
• Plane digitization and related combinatorial problems
• Discrete segments of \(\mathbb{Z}^3\) constructed by synchronization of words
• Word equations with \(k\)th powers of variables
• A generalization of the Fibonacci word fractal and the Fibonacci snowflake
• Another definition for digital tangents
• Discrete geometry and symbolic dynamics
• The perimeter of uniform and geometric words: a probabilistic analysis
• Minimal non-convex words
• Combinatorial View of Digital Convexity
• Number of Words Characterizing Digital Balls on the Triangular Tiling
• Lyndon + Christoffel = digitally convex

This page was built for publication: Interactions between digital geometry and combinatorics on words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789507)