Treffer: On the min DSS problem of closed discrete curves
Title:
On the min DSS problem of closed discrete curves
Authors:
Source:
IWCIA 2003 - Ninth International Workshop on Combinatorial Image AnalysisDiscrete applied mathematics. 151(1-3):138-153
Publisher Information:
Amsterdam; Lausanne; New York, NY: Elsevier, 2005.
Publication Year:
2005
Physical Description:
print, 9 ref
Original Material:
INIST-CNRS
Subject Terms:
Control theory, operational research, Automatique, recherche opérationnelle, Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Analyse mathématique, Mathematical analysis, Calcul des variations et contrôle optimal, Calculus of variations and optimal control, Géométrie, Geometry, Géométrie convexe et discrète, Convex and discrete geometry, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Algorithme optimal, Optimal algorithm, Algoritmo óptimo, Complexité algorithme, Algorithm complexity, Complejidad algoritmo, Informatique théorique, Computer theory, Informática teórica, Méthode optimisation, Optimization method, Método optimización, Temps linéaire, Linear time, Tiempo lineal, Courbe discrète, Discrete curve, Couverture tangentielle, Tangential cover, Problème min DSS, Min DSS problem, Segment discret, Discrete segment, Discrete curves and segments: Tangential cover, Optimal complexity
Document Type:
Konferenz
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
LLAICI - IUT Clermont-Ferrand, Campus des Cézeaux, BP 86, 63172 Aubière, France
Laboratoire LIRIS, Université Lumière Lyon2, 5, avenue Pierre-Mendès-France, 69676 Bron, France
Laboratoire LIRIS, Université Lumière Lyon2, 5, avenue Pierre-Mendès-France, 69676 Bron, France
ISSN:
0166-218X
Rights:
Copyright 2005 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Mathematics
Mathematics
Accession Number:
edscal.17157695
Database:
PASCAL Archive
Weitere Informationen
Given a discrete eight-connected curve, it can be represented by discrete eight connected segments. In this paper, we try to determine the minimal number of necessary discrete segments. This problem is known as the min DSS problem. We propose to use a generic curve representation by discrete tangents, called a tangential cover which can be computed in linear time. We introduce a series of criteria each having a linear-time complexity to progressively solve the min DSS problem. This results in an optimal algorithm both from the point of view of optimization and of complexity, outperforming the previous quadratic bound.