HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Detection of the Discrete Convexity of Polyominoes

Isabelle Debled-Rennesson 1 Jean-Luc Rémy 1 Jocelyne Rouyer-Degli 1
1 ADAGE - Applying discrete algorithms to genomics
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 in 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, linear algorithm, whose correction is proven. Correlatively, we obtain a characterisation of lower and upper frontiers of the convex hull of a discrete line segment. Finally, we evoke some applications of these results to the problem of discrete tomography.
Document type :
Journal articles
Complete list of metadata

Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Tuesday, September 26, 2006 - 9:37:57 AM
Last modification on : Friday, February 4, 2022 - 3:21:48 AM


  • HAL Id : inria-00099507, version 1



Isabelle Debled-Rennesson, Jean-Luc Rémy, Jocelyne Rouyer-Degli. Detection of the Discrete Convexity of Polyominoes. Discrete Applied Mathematics, Elsevier, 2003, 125 (1), pp.115-133. ⟨inria-00099507⟩



Record views