Discrete Geometry and Word Combinatorics - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2009

Discrete Geometry and Word Combinatorics

Valerie Berthe


The aim of this lecture is to show how discrete geometry and word combinatorics can interact through the study of the most basic objects in discrete geometry, namely arithmetic discrete planes. In word combinatorics, Sturmian words and regular continued fractions are known to provide a very fruitful interaction between arithmetics, discrete geometry and symbolic dynamics. Recall that Sturmian words are infinite words which code irrational discrete lines over a two-letter alphabet. Most combinatorial properties of Sturmian words can be described in terms of the continued fraction expansion of the slope of the discrete line that they code. Our aim here is to show how to extend this interaction to higher dimensions. Special focus will be given to a generation method for discrete planes based on a formalism extending to the multidimensional case morphisms of the free monoid. The role played respectively by words and classical continued fractions will be played by stepped surfaces (which are discretizations of two-dimensional surfaces embedded in the three-dimensional space) and generalized unimodular Euclidean algorithms. We will use the fact that we can describe an arithmetic discrete plane either as a tiling of the plane by three kinds of lozenges (after projection), or else, as a multidimensional word over a three-letter alphabet (after coding).
No file

Dates and versions

lirmm-00389856 , version 1 (29-05-2009)


  • HAL Id : lirmm-00389856 , version 1


Valerie Berthe. Discrete Geometry and Word Combinatorics. CanaDAM'09: 2nd Canadian Discrete and Algorithmic Mathematics Conference, May 2009, Canada. ⟨lirmm-00389856⟩
60 View
0 Download


Gmail Mastodon Facebook X LinkedIn More