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.
2017
9783319663951
978-3-319-66396-8
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].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1035030