Weber, Romaine Ariane
(2015).
« Un algorithme linéaire pour le calcul de l'enveloppe externe d'un chemin discret » Mémoire.
Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique.
Fichier(s) associé(s) à ce document :
Résumé
Ce mémoire concerne le problème du calcul de l'enveloppe externe d'une figure et se situe dans le domaine de la géométrie digitale, une branche importante de la géométrie discrète et algorithmique. Le point de vue adopté est intimement lié à la combinatoire des mots puisque toute figure discrète est codée par son contour, c'est-à-dire un mot sur l'alphabet de Freeman constitué de quatre lettres identifiant les quatre directions élémentaires sur le réseau carré Z x Z, qui représente notre plan discret. Ainsi le problème se réduit à étudier les mots de contour. On présente donc un algorithme permettant de calculer l'enveloppe externe d'un chemin discret. On utilise une structure d'arbre quaternaire pour représenter les points du plan discret Z x Z, enrichie par des liens de voisinages. En assimilant notre chemin discret à un labyrinthe, l'algorithme de calcul de l'enveloppe externe se base sur la méthode bien connue dite "de la main droite" permettant de sortir d'un labyrinthe efficacement. De plus, grâce à la structure d'arbre quaternaire, notre algorithme est linéaire en temps et en espace.
| Type: |
Mémoire accepté
|
| Informations complémentaires: |
Le mémoire a été numérisé tel que transmis par l'auteur. |
|
Directeur de thèse: |
Brlek, Srecko |
| Mots-clés ou Sujets: |
Enveloppes (Géométrie) / Algorithmes / Géométrie discrète / Géométrie algorithmique / Géométrie convexe / Combinatoire des mots |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
22 avr. 2016 19:09 |
| Dernière modification: |
22 avr. 2016 19:09 |
| Adresse URL : |
http://archipel.uqam.ca/id/eprint/8271 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
