First Steps in the Algorithmic Reconstruction of Digital Convex Sets

摘要

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, Provencal and Reutenauer (see [4]) on this topic sets a bridge between digital convexity and combinatorics on words: the boundary word of a DC poly-omino 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.