Nous abordons dans cette étude le problème de la reconstruction de courbes et de surfaces, à partir de points leur appartenant et sous l'hypothèse que la seule connaissance que nous avons sur ces points est celle de leurs coordonnées. Dans le cas des courbes, nous proposons une méthode basée sur l'approximation locale de la courbe par des cercles et sur le traitement global de sous-ensembles de points. Une méthode d'approximation robuste au moyen d'un problème de minimisation permet donc d'approcher localement la courbe par un cercle, et d'ordonner les sous-ensembles de points ainsi approchés. Des méthodes algorithmiques de découpe et de raccord permettent alors de mener à bien la reconstruction d'une courbe. L'existence de points multiples ou de points de rebroussement est prise en compte par une stratégie d'énumération des différentes morphologies locales de la courbe. La méthode s'avère aussi robuste lorsque les points initiaux sont perturbés. Les complexités temporelle et en place mémoire optimales des algorithmes et de la structure de données, ainsi que l'ordonnancement global permettent de traiter des ensembles initiaux comportant un grand nombre de points. Des cas de surfaces radiales ou de surfaces correspondant au graphe d'une fonction ont été traités en approchant le nuage de points par une sphère. Les points sont projetés et triangulés selon la triangulation de Delaunay sur la sphère, et nous obtenons alors une surface polyèdrique liant les points. Des tests et des comparaisons avec des méthodes du type triangulations dépendantes des données sont établis sur ces catégories de surfaces

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.

Esta tesis se divide en dos partes. La primera parte contiene el estudio de tres pesos o profundidades, asociados a conjuntos finitos de puntos en el plano: el peso definido por las capas convexas, convex depth (introducido por Hubert (72) y Barnett (76)), la separabilidad lineal, también conocido por location, halfspace o Tukey depth (Tukey 75) y el peso Delaunay (Green 81). De la noción de peso, se obtiene una estratificación de los conjuntos de puntos en el plano en capas y una partición del plano en regiones o niveles, cuyas fronteras son conocidas por depth contours. Se definen los conceptos de capa y nivel en los tres pesos señalados y se estudian sus propiedades y complejidades. Chazelle obtuvo métodos para hallar en tiempo óptimo las capas convexas, que coinciden con las fronteras de los niveles convexos. En esta tesis, para los pesos de separabilidad lineal y Delaunay, se proporcionan algoritmos de obtención, tanto de capas como de niveles, y de cálculo del peso de un punto nuevo que se incorpore a la nube. De forma independiente, han sido obtenidos para el peso de la separabilidad lineal los algoritmos de construcción de los niveles, location depth contours, y el de cálculo del peso de un punto nuevo, por Miller et al. (01). Para los tres pesos mencionados, se analizan árboles generadores, poligonizaciones o triangulaciones, con peso mínimo, donde el peso se ha considerado como la suma de los pesos de las aristas de dichas estructuras. Se obtienen propiedades generales entorno a la caracterización de tales estructuras y algoritmos de obtención para alguna de ellas. Se definen dos pesos relacionados con la separabilidad mediante cuñas: el peso según dominación isotética y la separabilidad . En ambos, se dan algoritmos para el cálculo de los pesos de los puntos de un conjunto dado. La separabilidad  está estrechamente relacionada con la enumeración eficiente de (,k)-sets. Se realiza un estudio combinatorio del conjunto de (,k)-sets para nubes de puntos en el plano y se describen algoritmos de construcción de todos los (,k)-sets en cada uno de los cuatro casos posibles, según sean,  o k, fijos o variables. En la segunda parte, se tratan diversos problemas de transversalidad. Se obtienen resultados acerca de la caracterización de las permutaciones realizables, tanto como polígonos simples, como convexos, sobre arreglos de rectas. Para colecciones de segmentos en el plano, se definen cuña y círculo transversales separadores. Se realiza un análisis del orden de estos elementos transversales separadores y se obtienen diversos algoritmos de decisión de existencia de los mismos y construcción de todos ellos. Para colecciones de círculos, también se define el círculo transversal separador y se obtiene un algoritmo de existencia y construcción de dichos círculos para círculos con el mismo radio. / This thesis can be divided into two parts. The first part contains the study of three weights or depths associated to finite point sets in the plane: the convex depth convex hull peeling depth (introduced by Hubert (72) and Barnett (76)), the location depth (also known by halfspace or Tukey depth (Tukey (75)), and the Delaunay depth (Green (81)).From any notion of depth, a stratification of the point sets of the plane into layers and a partition of the plane into regions or levels are obtained. The boundaries of the levels are known by depth contours. We define the concepts of layers and levels for all three depths and we study their properties and their complexities. Chazelle obtained methods to find the layers, which are the boundaries of the convex levels, with an optimal time algorithm. We present the algorithms for constructing the layers and levels, in location and Delaunay depths. Also, for both depths, we show algorithms to calculate the depth of a new point joining the cloud. In an independent way, the algorithms to obtain the levels (location depth contours) and to calculate the location depth of a new point, are obtained by Miller et al. (01).For each one of the three mentioned depths, we study the geometric structures (spanning trees, polygonizations and triangulations) with minimum weight, where this weight has been considered as t-weight (the addition of the weight of their edges). We obtain general properties about the characterization of such structures and some algorithms to obtain them. We define two depths related with the separability by wedges: the isothetic-domination and the -separability which generalizes the location depth. We develop the algorithms in order to obtain the depths of all points of a given set in both cases. The -separability (in particular the location depth) is closely related with the efficient enumeration of the (,k)-sets. We make a combinatorial study of the (,k)-sets for point sets in the plane. We give lower and upper bounds for the maximum number of the (,k)-sets and we give algorithms for constructing all them, in each one of the four cases according to the case where  or k are fixed or variable.In the second part, we consider some transversality problems. We obtain results about the characterization of the realizable permutations both as simple and as convex polygons, over arrangements of lines. We also study some transversality problems with wedges and circles. We have defined the separating transversal wedge and the separating transversal circle for sets of segments. We analyze the size of the set of the transversal elements. Furthermore, we obtain some decision algorithms on the existence and construction of all of them. Finally, we define also the separating transversal circle for sets of circles and we obtain an algorithm for sets of circles with the same radius.

This thesis presents the numerical algorithms to carry out the face transformation. The main efforts are denoted to the finite volume method (FVM) with the Delaunay triangulation to solve the Laplace equations in the harmonic transformation undergone in face images. The advantages of the FVM with the Delaunay triangulation are: (1) Easy to formulate the linear algebraic equations, (2) Good to retain the geometric and physical properties, (3) less CPU time needed. The numerical and graphical experiments are reported for the face transformations from a female to a male, and vice versa. The computed sequential and absolute errors are and , where N is division number of a pixel into subpixels. Such computed errors coincide with the analysis on the splitting-shooting method (SSM) with piecewise constant interpolation in [Li and Bui, 1998c].

This thesis is a contribution to a classical problem in computational and combinatorial geometry: the study of the k-sets of a set V of n points in the plane. First we introduce the notion of convex inclusion chain that is an ordering of the points of V such that no point is inside the convex hull of the points that precede it. Every k-set of an initial sub-sequence of the chain is called a k-set of the chain. We prove that the number of these k-sets is an invariant of V and is equal to the number of regions in the order-k Voronoi diagram of V. We then deduce an online algorithm for the construction of the k-sets of the vertices of a simple polygonal line such that every vertex of this line is outside the convex hull of all its preceding vertices on the line. If c is the total number of k-sets built with this algorithm, the complexity of our algorithm is in O(n log n + c log^2k) and is equal, per constructed k-set, to the complexity of the best algorithm known. Afterward, we prove that the classical divide and conquer algorithmic method can be adapted to the construction of the k-sets of V. The algorithm has a complexity of O(n log n + c log^2k log(n/k)), where c is the maximum number of k-sets of a set of n points. We finally prove that the centers of gravity of the k-sets of a convex inclusion chain are the vertices of a triangulation belonging to the family of so-called centroid triangulations. This family notably contains the dual of the order-k Voronoi diagram. We give an algorithm that builds particular centroid triangulations in O(n log n + k(n- k) log^2 k) time, which is more efficient than all the currently known algorithms.

Ce mémoire traite de la compression des images fixes par fractales, fondée sur la théorie des systèmes de fonctions itérées (IFS). Après quelques rappels sur les principales méthodes de codage entropique et de compression réversible et irréversible des images nous introduisons les notions nécessaires à la compréhension de la théorie des IFS. Nous détaillons ensuite les principaux algorithmes de compression des images naturelles selon l'approche fractale. Ces derniers consistent à approximer chacun des éléments d'une partition à l'aide d'une transformation locale contractante appliquée sur une autre partie de l'image. Ceci nous conduit à présenter les modèles de partitionnement utilisés pour coder les similarités locales des images. La partie suivante constitue la contribution majeure du travail. Nous présentons un algorithme de codage par fractales fondé sur la triangulation de Delaunay. La souplesse de ce modèle nous permet d'utiliser diverses triangulations adaptées au contenu de l'image à compresser. Nous proposons ensuite différentes solutions ayant pour but d'améliorer le schéma de codage-decodage. La premiere vise à réduire la complexité de la phase de codage en diminuant le nombre de comparaisons inter-blocs, par un algorithme de quantification vectorielle de l'espace de recherche. La seconde vise à réduire le nombre de blocs traités tout en améliorant les résultats visuels, pour des taux de compression élevés. Ceci est fait en introduisant des quadrilatères dans la triangulation de l'image. Nous concluons le mémoire en commentant différents résultats de décompression obtenus à partir des partitionnements étudiés, puis comparons ces résultats à ceux obtenus à partir de méthodes hybrides liant le codage par fractales à une décomposition multirésolution de l'image ou à la transformée en cosinus discrète.

Thesis (MSc (Mathematical Sciences. Applied Mathematics))--University of Stellenbosch, 2007. / Image morphing is a popular technique used to create spectacular visual effects, by gradually transforming one image into another. This thesis explains what exactly is meant by the terms “image morphing” / “warping”, where it is used and how it is done. A few existing morphing techniques are described and finally an implementation using Delaunay triangulation and texture mapping is presented.