Lyndon + Christoffel=digitally convex

Brlek, S.; Lachaud, J.-O.; Provençal, Xavier et Reutenauer, Christophe (2009). « Lyndon + Christoffel=digitally convex ». Pattern Recognition, 42(10), pp. 2239-2246.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (248kB)

Résumé

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.

Type:	Article de revue scientifique
Mots-clés ou Sujets:	Digital Convexity, Lyndon words, Christoffel words, Convex hull
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Christophe Reutenauer
Date de dépôt:	28 avr. 2016 18:30
Dernière modification:	19 mai 2016 18:18
Adresse URL :	http://archipel.uqam.ca/id/eprint/8354

Modifier les métadonnées (propriétaire du document)

Statistiques