Skip to Main content Skip to Navigation
Conference papers

A Linear Algorithm for Polygonal Representations of Digital Sets

Hélène Dörksen-Reiter 1 Isabelle Debled-Rennesson 2
2 ADAGIO - Applying Discrete Algorithms to Genomics and Imagery
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Polygonal representations of digital sets with the same convexity properties allow a simple decomposition of digital boundaries into convex and concave parts. Representations whose vertices are boundary points, i.e. are integer numbers, attract most attention. The existing linear Algorithm UpPolRep computes polygonal representations with some uncorresponding parts. However, the algorithm is unable to decide if a corresponding polygonal representation still exists and in the case of existence it is unable to compute the representation. Studying situations where uncorrespondences appear we extended the algorithm. The extention does not change the time complexity. If a digital set possesses a corresponding representation then it detects this representation. Otherwise, it recognizes that such representation does not exist.
Document type :
Conference papers
Complete list of metadata
Contributor : Isabelle Debled-Rennesson <>
Submitted on : Wednesday, September 19, 2007 - 1:20:02 PM
Last modification on : Friday, February 26, 2021 - 3:28:08 PM

Links full text




Hélène Dörksen-Reiter, Isabelle Debled-Rennesson. A Linear Algorithm for Polygonal Representations of Digital Sets. 11th International Workshop on Combinatorial Image Analysis - IWCIA 2006, Jun 2006, Berlin, Germany. pp.307-319, ⟨10.1007/11774938_24⟩. ⟨inria-00173236⟩



Record views