Digital convex (DC) sets plays a prominent role in the framework of digital geometry providing a natural generalization to the concept of Euclidean convexity when we are dealing with polyominoes, i.e., finite and connected sets of points. A result by Brlek, Lachaud, Provençal and Reutenauer on this topic sets a bridge between digital convexity and combinatorics on words: the boundary word of a DC polyomino can be divided in four monotone paths, each of them having a Lyndon factorization that contains only Christoffel words. The intent of this paper is to provide some local properties that a boundary words has to fulfill in order to allow a single point modifications that preserves the convexity of the polyomino.
First Steps in the Algorithmic Reconstruction of Digital Convex Sets / Paolo, Dulio; Andrea, Frosini; Simone, Rinaldi; Lama, Tarsissi; Laurent, Vuillon. - STAMPA. - (2017), pp. 164-176. (Intervento presentato al convegno International Conference on Combinatorics on Words) [10.1007/978-3-319-66396-8_16].
First Steps in the Algorithmic Reconstruction of Digital Convex Sets
Andrea Frosini;Simone Rinaldi;TARSISSI, LAMA
;
2017
Abstract
Digital convex (DC) sets plays a prominent role in the framework of digital geometry providing a natural generalization to the concept of Euclidean convexity when we are dealing with polyominoes, i.e., finite and connected sets of points. A result by Brlek, Lachaud, Provençal and Reutenauer on this topic sets a bridge between digital convexity and combinatorics on words: the boundary word of a DC polyomino can be divided in four monotone paths, each of them having a Lyndon factorization that contains only Christoffel words. The intent of this paper is to provide some local properties that a boundary words has to fulfill in order to allow a single point modifications that preserves the convexity of the polyomino.
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
