Combinatorial view of digital convexity
S Brlek, JO Lachaud, X Provençal - … , DGCI 2008, Lyon, France, April 16-18 …, 2008 - Springer
S Brlek, JO Lachaud, X Provençal
Discrete Geometry for Computer Imagery: 14th IAPR International Conference …, 2008•SpringerThe 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.
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.
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.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果