Lyndon + Christoffel = digitally convex

摘要

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.