Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Aspects algorithmiques de la géométrie discrète

Tremblay Hugo. (2016). Aspects algorithmiques de la géométrie discrète. Thèse de doctorat, Université du Québec à Montréal.

[thumbnail of D3180.pdf]
Prévisualisation
PDF - Version publiée
11MB

URL officielle: https://archipel.uqam.ca/9305/

Résumé

Cette thèse étudie diverses notions en géométrie discrète d'un point de vue algorithmique. Plus particulièrement, elle fournit un cadre d'algorithmes efficaces afin de résoudre des problèmes concernant les figures discrètes en se basant uniquement sur l'étude du contour de ces dernières. Les résultats obtenus s'appuient principalement sur la théorie des graphes et leurs représentations, ainsi que sur la combinatoire des mots. La première théorie permet d'aborder les problèmes étudiés sous un angle géométrique, tandis que la seconde fournit un modèle simple et efficace pour le traitement et l'analyse de chemins et de figures discrètes. Les résultats développés au fil du texte appartiennent principalement aux domaines de la théorie des graphes, de la combinatoire des mots et de l'informatique théorique. En plus de ces contributions théoriques, ils trouvent aussi écho dans plusieurs autres domaines liés aux technologies de l'information, notamment en traitement d'images numériques ou, encore, en cristallographie. Ce document s'articule autour de trois sujets principaux, tous liés de près ou de loin à la notion centrale de polyominos, c'est-à-dire un ensemble de pixels connexes dans le plan discret Z2. Dans un premier temps, nous introduisons le concept de réseau parallélogramme, permettant ainsi d'établir de nouveaux résultats de nature algébrique sur un type particulier de morphisme appelé morphisme parallélogramme. Ensuite, nous étudions la notion de polyomino premier. Notamment, nous fournissons un algorithme polynomial de factorisation. Finalement, nous étudions diverses opérations géométriques fondamentales sur les polyominos. Notons que tous les algorithmes présentés ont été implémentés et testés sur plusieurs exemples. Ce travail de fin d'études constitue un apport aux mathématiques discrètes par l'établissement de nouveaux résultats. Parmi ceux-ci, mentionnons un algorithme linéaire pour le calcul des enveloppes externe et convexe de tout chemin discret de Z2 ainsi que des algorithmes linéaires afin de calculer l'union, l'intersection et la différence de polyominos.

Type de document:Thèse ou mémoire d'autres institutions (Thèse de doctorat)
Date:2016
Lieu de publication:Montréal
Programme d'étude:Doctorat en mathématiques
Nombre de pages:129
Sujets:Sciences naturelles et génie > Sciences mathématiques
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique
Directeur(s), Co-directeur(s) et responsable(s):Brlek, Srecko
Blondin Massé, Alexandre
Mots-clés:informatique, géométrie discrète, combinatoire des mots, topologie des graphes, algorithmique, polyominos
Déposé le:18 nov. 2020 20:49
Dernière modification:18 nov. 2020 20:49
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630