This repository has been archived by the owner on Apr 9, 2019. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 0
/
resume.tex
19 lines (8 loc) · 1.52 KB
/
resume.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
% !TEX root = memoire.tex
\begin{abstract}
La géométrie digitale est un domaine d'études développé récemment, à cause du développement des outils numériques.
Ce mémoire examine deux problèmes importants dans le domaine de la géométrie digitale, à savoir le calcul de l’enveloppe extérieure d’un chemin discret et également la génération exhaustive de polyominos. Les deux reposent sur le codage des objets dans le plan discret, assimilé à la grille carrée $\Z\times\Z$, par des mots sur l'alphabet de Freeman $\F=\{\ocr{0},\ocr{1},\ocr{2},\ocr{3}\}$, correspondant aux déplacements élémentaires sur la grille carrée.
Pour le problème de l'enveloppe extérieure d'un chemin quelconque (se recoupant ou pas), on utilise une structure de données utilisant deux arbres quaternaires superposés, introduite par Brlek, Provençal et Koskas. Utilisant un parcours mimant l'algorithme de la main droite dans un labyrinthe on obtient un algorithme linéaire en temps et en espace pour effectuer le calcul de l'enveloppe extérieure.
Dans le cas de la génération de polyominos codés par un chemin décrivant leurs périmètres de site, on utilise une adaptation du jeu de go pour construire à partir de l'origine et dans le sens antihoraire le chemin qui les borne. L'algorithme est exhaustif, et génère un polyomino chaque fois que le joueur noir gagne.
\textit{Mots-clés:} polyominos, gominos, périmètre de site, chemins, enveloppe externe, génération exhaustive, algorithme, mots, arbre radix.
\end{abstract}