Lyndon + Christoffel=digitally convex




  • handle:  10670/1.n3rq71
  • Brlek, S.; Lachaud, J.-O.; Provençal, Xavier et Reutenauer, Christophe (2009). « Lyndon + Christoffel=digitally convex ». Pattern Recognition, vol. 42, no 10, pp. 2239-2246. ISSN 00313203


Digital Convexity Lyndon words Christoffel words Convex hull

Similar subjects En

Convex regions Convexity

Cite this document

S. Brlek et al., « Lyndon + Christoffel=digitally convex », UQAM Archipel : articles scientifiques, ID : 10670/1.n3rq71


Share / Export

Abstract 0

Discrete geometry redefines notions borrowed from Euclidean geometry creating a need for new algorithmical tools. The notion of convexity does not translate trivially, and detecting if a discrete region of the plane is convex requires a deeper analysis. To the many different approaches of digital convexity, we propose the combinatorics on words point of view, unnoticed until recently in the pattern recognition community. In this paper we provide first a fast optimal algorithm checking digital convexity of polyominoes coded by their contour word. The result is based on linear time algorithms for both computing the Lyndon factorization of the contour word, and the recognition of Christoffel factors that are approximations of digital lines. By avoiding arithmetical computations the algorithm is much simpler to implement and much faster in practice. We also consider the convex hull computation and relate previous work in combinatorics on words with the classical Melkman algorithm.

From the same authors

On the same subjects