Interactions between Digital Geometry and Combinatorics on Words.

link: http://arxiv.org/abs/1108.3615
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.