Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Cette dernière décennie a vu apparaître et se développer toute une théorie sur l'échantillonnage des surfaces lisses. L'objectif était de trouver des conditions d'échantillonnage qui assurent une bonne reconstruction d'une surface lisse S à partir d'un sous-ensemble fini E de points de S. Parmi ces conditions, l'une des plus importantes est sans conteste la condition d'e-échantillonnage, introduite par Amenta et Bern, qui stipule que tout point p de S doit être à distance de E au plus e fois lfs(p), où lfs(p) désigne la distance de p à l'axe médian de S. Amenta et Bern ont montré qu'il est possible d'extraire de la triangulation de Delaunay d'un e-échantillon E une surface affine par morceaux qui approxime S du point de vue topologique (isotopie) et géométrique (distance de Hausdorff). Néanmoins restaient ouvertes les questions cruciales de pouvoir vérifier si un ensemble de points donné est un e-échantillon d'une part, et de construire des e-échantillons d'une surface lisse donnée d'autre part. De plus, les conditions d'échantillonnage proposées jusque là n'offraient des garanties que dans le cas lisse, puisque lfs s'annule aux points où la surface n'est pas différentiable. Dans cette thèse, nous introduisons le concept d'e-échantillon lâche, qui peut être vu comme une version faible de la notion d'e-échantillon. L'avantage majeur des e-échantillons lâches sur les e-échantillons classiques est qu'ils sont plus faciles à vérifier et à construire. Plus précisément, vérifier si un ensemble fini de points est un e-échantillon lâche revient à regarder si les rayons d'un nombre fini de boules sont suffisamment petits. Quand la surface S est lisse, nous montrons que les e-échantillons sont des e-échantillons lâches et réciproquement, à condition que e soit suffisamment petit. Il s'ensuit que les e-échantillons lâches offrent les mêmes garanties topologiques et géométriques que les e-échantillons. Nous étendons ensuite nos résultats au cas où la surface échantillonnée est non lisse en introduisant une nouvelle grandeur, appelée rayon Lipschitzien, qui joue un rôle similaire à lfs dans le cas lisse, mais qui s'avère être bien défini et positif sur une plus large classe d'objets. Plus précisément, il caractérise la classe des surfaces Lipschitziennes, qui inclut entre autres toutes les surfaces lisses par morceaux pour lesquelles la variation des normales aux abords des points singuliers n'est pas trop forte. Notre résultat principal est que, si S est une surface Lipschitzienne et E un ensemble fini de points de S tel que tout point de S est à distance de E au plus une fraction du rayon Lipschitzien de S, alors nous obtenons le même type de garanties que dans le cas lisse, à savoir : la triangulation de Delaunay de E restreinte à S est une variété isotope à S et à distance de Hausdorff O(e) de S, à condition que ses facettes ne soient pas trop aplaties. Nous étendons également ce résultat aux échantillons lâches. Enfin, nous donnons des bornes optimales sur la taille de ces échantillons. Afin de montrer l'intérêt pratique des échantillons lâches, nous présentons ensuite un algorithme très simple capable de construire des maillages certifiés de surfaces. Etant donné une surface S compacte, Lipschitzienne et sans bord, et un paramètre positif e, l'algorithme génère un e-échantillon lâche E de S de taille optimale, ainsi qu'un maillage triangulaire extrait de la triangulation de Delaunay de E. Grâce à nos résultats théoriques, nous pouvons garantir que ce maillage triangulaire est une bonne approximation de S, tant sur le plan topologique que géométrique, et ce sous des hypothèses raisonnables sur le paramètre d'entrée e. Un aspect remarquable de l'algorithme est que S n'a besoin d'être connue qu'à travers un oracle capable de détecter les points d'intersection de n'importe quel segment avec la surface. Ceci rend l'algorithme assez générique pour être utilisé dans de nombreux contextes pratiques et sur une large gamme de surfaces. Nous illustrons cette généricité à travers une série d'applications : maillage de surfaces implicites, remaillage de polyèdres, sondage de surfaces inconnues, maillage de volumes.

L'organisation structurée (graphe avec hiérarchies et propriétés sémantiques) d'objets du plan implique plusieurs opérations complexes qui doivent être effectuées en toute sécurité de cohérence topologique. La précision inhérente d'une machine étant nécessairement limitée, il faut souvent recourir à une arithmétique exacte couteuse. Cette thèse présente, à partir de travaux liés à la réalisation du module de facettisation d'un simulateur de vol industriel, une solution permettant l'utilisation d'une arithmétique mixte, de précision arbitraire et de coût très inférieur statistiquement a la solution exacte. On y trouve aussi l'unification des méthodes de construction d'un diagramme de Voronoi, d'une triangulation de Delaunay pour un nuage de points dans le plan et de la triangulation contrainte de Delaunay de la représentation par segments d'un graphe planaire, autour d'une technique incrémentale optimale, fondamentalement plus simple que la méthode diviser-pour-résoudre classique. La technique incrémentale permet, par ailleurs, de donner un algorithme linéaire et très simple de construction du diagramme de Voronoi et de la triangulation de Delaunay d'un nuage de points situes sur la frontière d'un polygone monotone ou convexe.

Les cytochromes P450s (CYPs) sont des hémoprotéines intervenant dans la fonction de détoxication cellulaire. Le site actif des CYPs est enfoui dans la protéine, mais accessible aux ligands par des canaux. A l'aide d'une méthode récente basée sur la triangulation de Delaunay de la protéine, et implémentée dans le logiciel CCCPP, nous avons modélisé géométriquement ces canaux pour plusieurs isoformes humaines, dont le 3A4, présent au niveau du foie humain et responsable de la métabolisation d'un nombre important de médicaments, afin de constituer un filtre stérique destiné au criblage virtuel rapide de chimiothèques. Cette approche nous a permis d'obtenir des informations sur les mécanismes d'ouverture et de fermeture des canaux, permettant d'expliquer comment des ligands volumineux peuvent accéder au site actif. Ces résultats confirment et étendent ceux de la littérature, et peuvent contribuer à l'élaboration de médicaments nouveaux ou ayant moins d'effets secondaires. / The cytochromes P450s (CYPs) are hemoproteins involved in the cellular detoxification function. The CYPs active site is buried inside the protein, but it can be accessed by the ligands through channels. With a recent method based upon the Delaunay triangulation of the protein, and implemented in the CCCPP software, we modelized geometrically these channels for several human isoforms, including the 3A4, located in the human liver and responsible of the metabolization of an important number of drugs, in order to build a sterical filter devoted to high throughput virtual screening of chemical libraries. This approach let us to get information on mechanisms of opening and closing of the channels, allowing to explain how large ligands can access to the active site. These results are in agreement and extend those found in the literature, and can contribute to the design of new drugs or of drugs having less side effects.

La surface de Bolza est la surface hyperbolique orientable compacte la plus symétrique de genre 2. Pour tout genre supérieur à 2, il existe une surface orientable compacte construite de manière similaire à la surface de Bolza et ayant le même type de symétries. Nous appelons ces surfaces des surfaces hyperboliques symétriques. Cette thèse porte sur le calcul des triangulations de Delaunay (TD) de surfaces hyperboliques symétriques. Les TD de surfaces compactes peuvent être considérées comme des TD périodiques de leur revêtement universel (dans notre cas, le plan hyperbolique). Une TD est pour nous un complexe simplicial. Cependant, les ensembles de points ne définissent pas tous une décomposition simpliciale d'une surface hyperbolique symétrique. Dans la littérature, un algorithme a été proposé pour traiter ce problème avec l'utilisation de points factices : initialement une TD de la surface est construite avec un ensemble de points connu, puis des points d'entrée sont insérés avec le célèbre algorithme incrémental de Bowyer, et enfin les points factices sont supprimés, si la triangulation reste toujours un complexe simplicial. Pour la surface de Bolza, les points factices sont spécifiés. L'algorithme existant calcule une DT de la surface de Bolza comme une DT périodique du plan hyperbolique, ce qui nécessite de travailler dans un sous-ensemble approprié du plan hyperbolique. Nous étudions les propriétés des TD de la surface de Bolza définies par des ensembles de points contenants l'ensemble proposé de points factices, et nous décrivons en détail une implémentation de l'algorithme incrémentiel pour cette surface. Nous commençons par définir un représentant canonique unique qui est contenu dans un sous-ensemble borné du plan hyperbolique pour chaque face d'une TD de la surface. Nous donnons une structure de données pour représenter une TD de la surface de Bolza via les représentants canoniques de ses faces. Nous détaillons les étapes de la construction d'une telle triangulation et les opérations supplémentaires qui permettent de localiser les points et de retirer des sommets. Nous présentons également les résultats sur le degré algébrique des prédicats nécessaires pour toutes les opérations. Nous fournissons une implémentation entièrement dynamique pour la surface de Bolza, en offrant l'insertion de nouveaux points, la suppression des sommets existants, la localisation des points, et la construction d'objets duaux. Notre implémentation est basée sur la bibliothèque CGAL (Computational Geometry Algorithms Library), et est actuellement en cours de révision pour être intégrée dans la bibliothèque. L'intégration de notre code dans CGAL nécessite que tous les objets que nous introduisons soient compatibles avec le cadre existant et conformes aux standards adoptés par la bibliothèque. Nous donnons une description détaillée des classes utilisées pour représenter et traiter les triangulations hyperboliques périodiques et les objets associés. Des analyses comparatives et des tests sont effectués pour évaluer notre implémentation, et une application simple est donnée sous la forme d'une démonstration CGAL. Nous discutons une extension de notre implémentation à des surfaces hyperboliques symétriques de genre supérieur à 2. Nous proposons trois méthodes pour engendrer des ensembles de points factices pour chaque surface et présentons les avantages et les inconvénients de chaque méthode. Nous définissons un représentant canonique contenu dans un sous-ensemble borné du plan hyperbolique pour chaque face d'une TD de la surface. Nous décrivons une structure de données pour représenter une telle triangulation via les représentants canoniques de ses faces, et donnons des algorithmes pour l'initialisation de la triangulation. Enfin, nous discutons une implémentation préliminaire dans laquelle nous examinons les difficultés d'avoir des prédicats exacts efficaces pour la construction de TD de surfaces hyperboliques symétriques / The Bolza surface is the most symmetric compact orientable hyperbolic surface of genus 2. For any genus higher than 2, there exists one compact orientable surface constructed in a similar way as the Bolza surface having the same kind of symmetry. We refer to this family of surfaces as symmetric hyperbolic surfaces. This thesis deals with the computation of Delaunay triangulations of symmetric hyperbolic surfaces. Delaunay triangulations of compact surfaces can be seen as periodic Delaunay triangulations of their universal cover (in our case, the hyperbolic plane). A Delaunay triangulation is for us a simplicial complex. However, not all sets of points define a simplicial decomposition of a symmetric hyperbolic surface. In the literature, an algorithm has been proposed to deal with this issue by using so-called dummy points: initially a triangulation of the surface is constructed with a set of dummy points that defines a Delaunay triangulation of the surface, then input points are inserted with the well-known incremental algorithm by Bowyer, and finally the dummy points are removed, if the triangulation remains a simplicial complex after their removal. For the Bolza surface, the set of dummy points to initialize the triangulation is given. The existing algorithm computes a triangulation of the Bolza surface as a periodic triangulation of the hyperbolic plane and requires to identify a suitable subset of the hyperbolic plane in which to work. We study the properties of Delaunay triangulations of the Bolza surface defined by sets of points containing the proposed set of dummy points, and we describe in detail an implementation of the incremental algorithm for it. We begin by identifying a subset of the hyperbolic plane that contains at least one representative for each face of a Delaunay triangulation of the surface, which enables us to define a unique canonical representative in the hyperbolic plane for each face on the surface. We give a data structure to represent a Delaunay triangulation of the Bolza surface via the canonical representatives of its faces in the hyperbolic plane. We detail the construction of such a triangulation and additional operations that enable the location of points and the removal of vertices. We also report results on the algebraic degree of predicates needed for all operations. We provide a fully dynamic implementation for the Bolza surface, supporting insertion of new points, removal of existing vertices, point location, and construction of dual objects. Our implementation is based on CGAL, the Computational Geometry Algorithms Library, and is currently under revision for integration in the library. To incorporate our code into CGAL, all the objects that we introduce must be compatible with the existing framework and comply with the standards adopted by the library. We give a detailed description of the classes used to represent and handle periodic hyperbolic triangulations and related objects. Benchmarks and tests are performed to evaluate our implementation, and a simple application is given in the form of a CGAL demo. We discuss an extension of our implementation to symmetric hyperbolic surfaces of genus higher than 2. We propose three methods to generate sets of dummy points for each surface and present the advantages and shortcomings of each method. We identify a suitable subset of the hyperbolic plane that contains at least one representative for each face of a Delaunay triangulation of the surface, and we define a canonical representative in the hyperbolic plane for each face on the surface. We describe a data structure to represent such a triangulation via the canonical representatives of its faces, and give algorithms for the initialization of the triangulation with dummy points. Finally, we discuss a preliminary implementation in which we examine the difficulties of having efficient exact predicates for the construction of Delaunay triangulations of symmetric hyperbolic surfaces

Étant donné un ensemble S de points du plan, une triangulation de S est une décomposition de l'enveloppe convexe de S en triangles dont les sommets sont les points de S. Une triangulation de S est dite de Delaunay si le cercle circonscrit à chaque triangle ne contient aucun point de S en son intérieur. Dans cette thèse, nous étudions une généralisation de ces notions à un ensemble S de segments disjoints du plan.<br />Nous commençons par définir une nouvelle famille de diagrammes, appelés triangulations de segments. Nous étudions leurs propriétés géométriques et topologiques et nous donnons un algorithme pour construire efficacement une telle triangulation.<br />Nous généralisons ensuite la notion de triangulation de Delaunay aux triangulations de segments et nous mettons en évidence la dualité avec le diagramme de Voronoï de segments.<br />Nous étendons également la légalité des arêtes au cas des triangulations de segments en définissant, d'une part, la légalité géométrique qui caractérise la triangulation de Delaunay de segments parmi l'ensemble de toutes les triangulations de segments possibles et, d'autre part, la légalité topologique qui caractérise les triangulations de segments qui ont la même topologie que celle de Delaunay.<br />Enfin, nous décrivons un algorithme de « flip » qui transforme toute triangulation de segments en une triangulation qui a la même topologie que celle de Delaunay. À l'aide de fonctions localement convexes, nous démontrons que la suite de triangulations construites par cet algorithme converge vers celle de Delaunay et nous prouvons qu'une triangulation de segments qui a la même topologie que celle de Delaunay est obtenue après un nombre fini d'étapes.

Une tessellation de Voronoï est un moyen de diviser l'espace 3D en régions associées avec chaque élément d'un ensemble discret de points dans le but de caractériser leurs relations topologiques. Le processus associe à chacun de ces éléments un polyèdre, appelé cellule de Voronoï, défini par les intersections des plans de contact construits à mi chemin entre les points. Chaque cellule contient donc le voisinage le plus proche du point qui lui est associé et ses faces définissent les contacts avec ses plus proches voisins. Pour un ensemble donné de points, la décomposition en cellules de Voronoï est unique et absolue car il n'y a pas d'espace vide entre les cellules. De plus les caractéristiques des cellules telles que le nombre de face, le volume etc. sont des sources d'information utiles pour étudier l'organisation des points dans l'espace. Pour les structures protéiques deux échelles d'investigation peuvent être envisagées. Le niveau atomique qui est le plus représenté dans la littérature associe chaque cellule avec chaque atome ou groupe d'atomes présent dans la structure. Le second niveau associe chacune des cellules avec chaque résidu représenté par un point pouvant être un atome réel (le carbone alpha par exemple) ou un point virtuel comme le centre géométrique de la chaîne latérale. Le travail de thèse présenté ici décrit ces dernières tessellations tout d'abord d'un point de vue mathématique puis de manière plus concrète en l'appliquant aux structures protéiques et en étudiant les diverses propriétés des cellules. Deux applications concrètes sont ensuite présentées. La première est une étude statistique de la proximité des extrémités N terminale et C terminale des chaînes polypeptidiques, la seconde est une procédure d'attribution des structures secondaires régulières.

Dans cette thèse, nous étudions les triangulations définies par un ensemble de points dans des espaces de topologies différentes. Nous proposons une définition générale de la triangulation de Delaunay, valide pour plusieurs classes d'espaces, ainsi qu'un algorithme de construction. Nous fournissons une implantation pour le cas particulier du tore plat tridimensionnel. Ce travail est motivé à l'origine par le besoin de logiciels calculant des triangulations de Delaunay périodiques, dans de nombreux domaines dont l'astronomie, l'ingénierie des matériaux, le calcul biomédical, la dynamique des fluides, etc. Les triangulations périodiques peuvent être vues comme des triangulations du tore plat. Nous fournissons une définition et nous développons un algorithme incrémentiel efficace pour calculer la triangulation de Delaunay dans le tore plat. L'algorithme est adapté de l'algorithme incrémentiel usuel dans R^d. Au contraire des travaux antérieurs sur les triangulations périodiques, nous évitons de maintenir plusieurs copies périodiques des points, lorsque cela est possible. Le résultat fourni par l'algorithme est toujours une triangulation du tore plat. Nous présentons une implantation de notre algorithme, à présent disponible publiquement comme un module de la bibliothèque d'algorithmes géométriques CGAL. Nous généralisons les résultats à une classe plus générale d'espaces quotients plats, ainsi qu'à des espaces quotients de courbure constante positive. Enfin, nous considérons le cas du tore double, qui est un exemple de la classe beaucoup plus riche des espaces quotients de courbure négative constante.

Dans son environnement quotidien, l'homme est volontairement ou involontairement exposé à des champs électromagnétiques radiofréquences. La prédiction de l'élévation de température induite par ce rayonnement, à l'aide d'un calcul sur un modèle anatomique maillé, dépend beaucoup de la qualité de ce modèle. Les méthodes actuelles de génération de maillages volumiques utilisent des représentations surfaciques intermédiaires des données anatomiques. Nous montrons qu'il n'est pas nécessaire d'avoir une représentation surfacique pour générer un maillage volumique. Nous proposons une construction de maillages tétraédriques basée sur les diagrammes de Voronoi Centroïdaux et leur dual, la triangulation de Delaunay. Cette approche, contrairement aux approches de la littérature, traite directement un volume de voxels segmentés, obtenu par IRM ou par tomographie X, sans passer par une représentation surfacique. An d'obtenir des maillages, non plus uniformes mais adaptés à la complexité anatomique, nous avons proposé une nouvelle méthode de capture de cette complexité à l'aide d'une approximation de l'axe médian. Une comparaison, avec trois autres méthodes de génération de maillages de la littérature, montre que notre approche construit des tétraèdres de meilleure qualité géométrique pour différents critères. De cette qualité découle une meilleure précision sur la température induite par le rayonnement électromagnétique, calculée par une méthode d'éléments finis, ainsi qu'un temps de calcul réduit. Ces résultats montrent le potentiel de notre approche discrète de type "Voronoï-Delaunay" pour la génération de maillages tétraédriques.

Cette thèse s'articule autour de la reconstruction géométrique de formes. Plusieurs méthodes, basées sur les diagrammes de Voronoï, sont proposées pour la reconstruction automatique d'objets naturels. L'application principale est la modélisation et l'imagerie géologique. Une première méthode permet la reconstruction de volumes et surfaces géologiqu- es à partir de données incomplètes et hétérogènes : données ponctuelles sur des affleurements, portions de contours cartographiques, sondages, coupes incomplètes ou interprétées, modèles numériques de terrains... L'idée majeure de la méthode consiste à assembler les objets différents selon leurs proximités, en utilisant le diagramme de Voronoï de ces objets. Les diagrammes de Voronoï sont des structures géométriques permettant de partitionner l'espace en régions d'influence. En pratique toutes les données sont discrétisées en un ensemble de points colorés, les couleurs représentant ici les caractéristiques géologiques ou géophysiques des données, que nous souhaitons imager. La partition "colorée" de ces points nous donne une première solution topologique au problème de reconstruction. Elle nous fournit en outre, une représentation du bord de l'objet géologique et de son intérieur. L'utilisation de courbes et de surfaces déformables sous contraintes (tension, courbure et respect de la topologie initiale) permet ensuite d'obtenir des interfaces plus lisses et plus conformes. Une étape particulière permet de prendre en compte des surfaces de discontinui- té comme les failles. Afin de représenter un objet S, non plus par des éléments discrets (polyèdres de Voronoi), mais par les valeurs positives d'une fonction continue, nous avons introduit une nouvelle méthode. L'objectif de la méthode est de définir une fonction interpolante s telle que l'ensemble des zéros de s passe exactement par les données de départ et soit une approximation cohérente et lisse de S par ailleurs. Dans un premier temps nous définissons, une fonction caractéristique locale en chaque donnée (point, contour...) et l'objet volumique final résulte alors d'une interpolation de ces fonctions.