Detection of the Discrete Convexity of Polyominoes

Isabelle Debled-Rennesson 1 Jean-Luc Rémy 1 Jocelyne Rouyer-Degli 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The convexity of a discrete region is a property used in numerous domains of computational imagery. We study its detection iu the particular case of polyominoes. We present a first method, directly relying on its definition. A second method, which is based on techniques for segmentation of curves in discrete lines, leads to a very simple algorithm whose correctness is proven. Correlatively, we obtain a characterisation of lower and upper convex hulls of a discrete line segment. Finally, we evoke some applications of these results to the problem of discrete tomography.
Type de document :
Communication dans un congrès
G. Borgefors, A. Nyström, G. Sanniti di Baja. International Conference on Discrete Geometry for Computer Imagery - DGCI'2000, 2000, Uppsala, Suède, Springer-Verlag, 1953, pp.491-504, 2000, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00099095
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:50:53
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099095, version 1

Collections

Citation

Isabelle Debled-Rennesson, Jean-Luc Rémy, Jocelyne Rouyer-Degli. Detection of the Discrete Convexity of Polyominoes. G. Borgefors, A. Nyström, G. Sanniti di Baja. International Conference on Discrete Geometry for Computer Imagery - DGCI'2000, 2000, Uppsala, Suède, Springer-Verlag, 1953, pp.491-504, 2000, Lecture Notes in Computer Science. 〈inria-00099095〉

Partager

Métriques

Consultations de la notice

119