First Steps in the Algorithmic Reconstruction of Digital Convex Sets
| Autor: | Lama Tarsissi, Andrea Frosini, Simone Rinaldi, Laurent Vuillon, Paolo Dulio |
|---|---|
| Přispěvatelé: | Department of Mathematics and Computer Science / Dipartimento di Scienze Matematiche e Informatiche 'Roberto Magari' (DSMI), Università degli Studi di Siena = University of Siena (UNISI), Laboratoire de Mathématiques (LAMA), Centre National de la Recherche Scientifique (CNRS)-Université Savoie Mont Blanc (USMB [Université de Savoie] [Université de Chambéry]), Laboratoire d'informatique Algorithmique : Fondements et Applications (LIAFA), Université Paris Diderot - Paris 7 (UPD7)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
Polyomino
Computer science Boundary (topology) Discrete geometry Discrete tomography 02 engineering and technology [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Convexity Theoretical Computer Science Factorization Digital convexity Reconstruction problem Computer Science (all) Euclidean geometry 0202 electrical engineering electronic engineering information engineering Digital geometry 0101 mathematics Discrete mathematics Christoffel symbols 010102 general mathematics Regular polygon Monotone polygon 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Word Word, Aug 2017, Montreal, Canada. ⟨10.1007/978-3-319-66396-8⟩ Lecture Notes in Computer Science ISBN: 9783319663951 WORDS |
| DOI: | 10.1007/978-3-319-66396-8⟩ |
| Popis: | International audience; 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 con-vexity 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|