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

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.