Abstract
The notion of convexity translates non-trivially from Euclidean geometry to discrete geometry, and detecting if a discrete region of the plane is convex requires analysis. In this paper we study digital convexity from the combinatorics on words point of view, and provide a fast optimal algorithm checking digital convexity of polyominoes coded by the contour word. The result is based on the Lyndon factorization of the contour word, and the recognition of Christoffel factors that are approximations of digital lines.
Type
Publication
Proc. Int. Conf. Discrete Geometry for Computer Imagery (DGCI'2008), Lyon, France, volume 4992 of Lecture Notes in Computer Science, pp 57-68, 2008. Springer
Jacques-Olivier Lachaud
Professor of Computer Science
My research interests include digital geometry, geometry processing, image analysis, variational models and discrete calculus.