Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.

Given a set of points in the Euclidean plane, we are interested in its triangulations, i.e., the maximal sets of non-overlapping triangles with vertices in the given points whose union is the convex hull of the point set. With respect to the area of the triangles in a triangulation, several optimality criteria can be considered. We study two of them. The MaxMin area triangulation is the triangulation of the point set that maximizes the area of the smallest triangle in the triangulation. Similarly, the MinMax area triangulation is the triangulation that minimizes the area of the largest area triangle in the triangulation. In the case when the point set is in a convex position, we present algorithms that construct MaxMin and MinMax area triangulations of a convex polygon in $O(n^2log{n})$ time and $O(n^2)$ space. These algorithms are based on dynamic programming. They use a number of geometric properties that are established within this work, and a variety of data structures specific to the problems. Further, we study polynomial time computable approximations to the optimal area triangulations of general point sets. We present geometric properties, based on angular constraints and perfect matchings, and use them to evaluate the approximation factor and to achieve triangulations with good practical quality compared to the optimal ones. These results open new direction in the research on optimal triangulations and set the stage for further investigations on optimization of area.

We study the leading order asymptotics of a Random Matrix theory partition function related to colored triangulations. This partition function comes from a three Hermitian matrix model that has been introduced in the physics literature. We provide a detailed and precise description of the combinatorial objects that the partition function counts that has not appeared previously in the literature. We also provide a general framework for studying the leading order asymptotics of an N dimensional integral that one encounters studying the partition function of colored triangulations. The results are obtained by generalizing well know results for integrals coming from Hermitian matrix models with only one matrix that give the leading order asymptiotics in terms of a finite dimensional variational problem. We apply these results to the partition function for colored triangulations to show that the minimizing density of the variational problem is unique, and agrees with the one proposed in the physics literature. This provides the first complete mathematically rigorous description of the leading order asymptotics of this matrix model for colored triangulations.

No description available.

Cette thèse décrit et analyse un nouvel algorithme de génération de maillages tri-dimensionnels pour des domaines bornés par des surfaces lisses ou lisses par morceaux, c'est à dire des surfaces composées d'une collection de morceaux de surfaces lisses, joints en des courbes lisses. Cet algorithme utilise un processus glouton de raffinement de Delaunay et échantillonne l'intérieur et la frontière du domaine simultanément. Les résultats sont des maillages dont la qualité est certifiée, et où la taille des éléments est contrôlée par l'intermédiaire d'un champ de taille défini par l'utilisateur. L'analyse de l'algorithme montre de plus des guaranties sur la précision de l'approximation de la frontière du domaine, à condition que les angles entre deux morceaux de surfaces lisses soient supérieurs à 90°. La levée de cette limitation importante fera partie du travail de recherche qui suivra cette thèse. Une particularité intéressante de cet algorithme est qu'il ne nécessite de connaître le domaine qu'à travers un oracle capable de décider si un point de requête est à l'intérieur ou à l'extérieur du domaine, si un segment de droite intersecte ou non la frontière, et si un triangle intersecte les courbes lisses de la frontière. De ce fait, cet algorithme est générique et peut s'appliquer dans de nombreuses circonstances, allant du maillage d'objets définis par des surfaces implicites au maillage de domaines définis par une ou plusieurs zones dans une image tri-dimensionnelle, en passant par les objets dont la surface est déjà définie par un maillage triangulaire.

Scattered data collected at sample points may be used to determine simple functions to best fit the data. An ideal choice for these simple functions is bivariate splines. Triangulation of the sample points creates partitions over which the bivariate splines may be defined. But the optimality of the approximation is dependent on the choice of triangulation. An algorithm, referred to as an Edge Swapping Algorithm, has been developed to transform an arbitrary triangulation of the sample points into an optimal triangulation for representation of the scattered data. A Matlab package has been completed that implements this algorithm for any triangulation on a given set of sample points.

No description available.

Shifting attention from the plane to the sphere and torus, we extend the study of pseudo-triangulations. Planar representations of each surface are used. A number of theorems and concepts are taken from the plane and applied to the sphere and torus not only for pseudo-triangulations but for triangulations as well. We found the number of edges and faces in a triangulation on n vertices in the plane, on the sphere and on the torus.

Cette thèse est une contribution à un problème classique de la géométrie algorithmique et combinatoire : l’étude des k-sets d’un ensemble V de n points du plan. Nous introduisons d’abord la notion de chaîne d’inclusion de convexes qui est un ordonnancement des points de V tel qu’aucun point n’appartient à l’enveloppe convexe de ceux qui le précèdent. Tout k-set d’une sous-suite commençante de la chaîne est appelé un k-set de la chaîne. Nous montrons que le nombre de ces k-sets est un invariant de V et qu’il est égal au nombre de régions du diagramme de Voronoï d’ordre k de V. Nous en déduisons un algorithme en ligne pour construire les k-sets des sommets d’une ligne polygonale simple dont chaque sommet est à l’extérieur de l’enveloppe convexe des sommets qui le précèdent sur la ligne. Si c est le nombre total de k-sets construits, la complexité de notrealgorithme est en O(n log n+c log^2 k) et est équivalente, par k-set construit, à celle du meilleur algorithme connu. Nous montrons ensuite que la méthode algorithmique classique de division-fusion peut être adaptée à la construction des k-sets de V. L’algorithme qui en résulte a une complexité enO(n log n+c log^2 k log(n/k)), où c est le nombre maximum de k-sets d’un ensemble de n points.Nous prouvons enfin que les centres de gravité des k-sets d’une chaîne d’inclusion de convexes sont les sommets d’une triangulation qui appartient à la même famille de triangulations, dites centroïdes, que le dual du diagramme de Voronoï d’ordre k. Nous en d´déduisons un algorithme qui construit des triangulations centroïdes particulières en temps O(n log n+k(n-k) log^2 k), ce qui est plus efficace que les algorithmes connus jusque là. / 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.

The problem of selecting the connectivity of a triangulation in order to minimize a given cost function is studied. This problem is of great importance for applications, such as generating triangle mesh models of images and other bivariate functions. In early work, a well-known method named the local optimization procedure (LOP) was proposed by Lawson for solving the triangulation optimization problem. More recently, Yu et al. proposed a variant of the LOP called the LOP with lookahead (LLOP), which has proven to be more effective than the LOP. Unfortunately, each of the LOP and LLOP can only guarantee to yield triangulations that satisfy a weak optimality condition for most cost functions. That is, the triangulation optimized by the LOP or LLOP is only guaranteed to be such that no single edge flip can reduce the triangulation cost. In this thesis, a new optimality criterion named n-flip optimality is proposed, which has proven to be a useful tool for analyzing the optimality property. We propose a more general framework called the modified LOP (MLOP), with several free parameters, that can be used to solve the triangulation-cost optimization problem. By carefully selecting the free parameters, two MLOP-based methods called the MLOPB(L,M) and MLOPC(L) are derived from this framework. According to the optimality property introduced in the thesis, we have proven our proposed methods can satisfy a stronger optimality condition than the LOP and LLOP. That is, the triangulation produced by our MLOP-based methods cannot have their cost reduced by any single edge flip or any two edge flips. Due to satisfying this stronger optimality condition, our proposed methods tend to yield triangulations of significantly lower cost than the LOP and LLOP methods. In order to evaluate the performance of our MLOP-based methods, they are compared with two other competing approaches, namely the LOP and LLOP. Experimental results show that the MLOPB and MLOPC methods consistently yield triangulations of much lower cost than the LOP and LLOP. More specifically, our MLOPB and MLOPC methods yield triangulations with an overall median cost reduction of 16.36% and 16.62%, respectively, relative to the LOP, while the LLOP can only yield triangulations with an overall median cost reduction of 11.49% relative to the LOP. Moreover, our proposed methods MLOPB(2,i) and MLOPA(i) are shown to produce even better results if the parameter i is increased at the expense of increased computation time. / Graduate