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 (see [4]) 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.
Dulio, P., Frosini, A., Rinaldi, S., Tarsissi, L., Vuillon, L. (2017). First steps in the algorithmic reconstruction of digital convex sets. In Combinatorics on Words. WORDS 2017 (pp.164-176). Springer Verlag [10.1007/978-3-319-66396-8_16].
First steps in the algorithmic reconstruction of digital convex sets
Rinaldi, Simone;
2017-01-01
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 (see [4]) 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 IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1035030