Malhas simpliciais são utilizadas em várias áreas da Computação Gráfica e Engenharia, como por exemplo, em vizualização, simulação, prototipação, além de outras aplicações. Este tipo de malha é, geralmente, utilizada como aproximações discretas de espaços contínuos, onde eles oferecem representações flexíveis e eficientes. Muito esforço é gasto visando gerar malhas de boa qualidade, porém, em alguns casos as malhas acabam sendo modificadas. Entretanto, este tipo de operação é geralmente custosa e inflexível, o que pode resultar na geraão de malhas bem diferentes das originais. A habilidade de manipular cenas dinâmicas revela-se um dos problemas mais desafiadores da computação gráfica. Este trabalho propõe um método alternativo para atualizar malhas simpliciais que vai além de mudanças geométricas e topológicas. Tal método explora uma das propriedade das Tringulações de Delaunay com Pesos, que permite a usá-las para definir implicitamente as relações de conectividade de uma malha. Ao contrário de manter as informações de conectividade explicitamente, a atual abordagem simplesmente armazena uma coleção de pesos associados a cada vértice. Além disso, criamos um algoritmo para calcular uma Tringulação de Delaunay com Pesos a partir de uma dada triangulação. O algoritmo consiste em uma busca em largura que atribui pesos aos vértices, e uma estratégia de de subdivisão para assegurar que a triangulação reconstruída será correspondente à original. Este método apresenta diversas aplicações e, em particular, permite a criação de um sistema simples de realizar combinação entre triangulações, que será ilustrada com exemplos em 2D e 3D. / Simplicial meshes are used in many fields of Computer Graphics and Engineering, for instance, in visualization, simulation, prototyping, among other applications. This kind of mesh is often used as discrete approximations of continuous spaces, where they offer flexible and efficient representations. Considerable effort is spent in generating good quality meshes, but in some applications the meshes can be modified over time. However, this kind of operation is often very expensive and inflexible, sometimes leading to results very different from the original meshes. The ability to handle dynamic scenes reveals itself as one of the most challenging problems in computer graphics. This work proposes an alternative technique for updating simplicial meshes that undergo geometric and topological changes. It explores the property that a Weighted Delaunay Triangulation (WDT) can be used to implicitly define the connectivity of a mesh. Instead of explicitly maintaining connectivity information, this approach simply keeps a collection of weights associated to each vertex. It consists of an algorithm to compute a WDT from any given triangulation, which relies on a breadth-first traversal to assign weights to vertices, and a subdivision strategy to ensure that the reconstructed triangulation conforms with the original one. This technique has many applications and, in particular, it allows for a very simple method of merging triangulations, which is illustrated with both 2D and 3d examples.

Malhas simpliciais são utilizadas em várias áreas da Computação Gráfica e Engenharia, como por exemplo, em vizualização, simulação, prototipação, além de outras aplicações. Este tipo de malha é, geralmente, utilizada como aproximações discretas de espaços contínuos, onde eles oferecem representações flexíveis e eficientes. Muito esforço é gasto visando gerar malhas de boa qualidade, porém, em alguns casos as malhas acabam sendo modificadas. Entretanto, este tipo de operação é geralmente custosa e inflexível, o que pode resultar na geraão de malhas bem diferentes das originais. A habilidade de manipular cenas dinâmicas revela-se um dos problemas mais desafiadores da computação gráfica. Este trabalho propõe um método alternativo para atualizar malhas simpliciais que vai além de mudanças geométricas e topológicas. Tal método explora uma das propriedade das Tringulações de Delaunay com Pesos, que permite a usá-las para definir implicitamente as relações de conectividade de uma malha. Ao contrário de manter as informações de conectividade explicitamente, a atual abordagem simplesmente armazena uma coleção de pesos associados a cada vértice. Além disso, criamos um algoritmo para calcular uma Tringulação de Delaunay com Pesos a partir de uma dada triangulação. O algoritmo consiste em uma busca em largura que atribui pesos aos vértices, e uma estratégia de de subdivisão para assegurar que a triangulação reconstruída será correspondente à original. Este método apresenta diversas aplicações e, em particular, permite a criação de um sistema simples de realizar combinação entre triangulações, que será ilustrada com exemplos em 2D e 3D. / Simplicial meshes are used in many fields of Computer Graphics and Engineering, for instance, in visualization, simulation, prototyping, among other applications. This kind of mesh is often used as discrete approximations of continuous spaces, where they offer flexible and efficient representations. Considerable effort is spent in generating good quality meshes, but in some applications the meshes can be modified over time. However, this kind of operation is often very expensive and inflexible, sometimes leading to results very different from the original meshes. The ability to handle dynamic scenes reveals itself as one of the most challenging problems in computer graphics. This work proposes an alternative technique for updating simplicial meshes that undergo geometric and topological changes. It explores the property that a Weighted Delaunay Triangulation (WDT) can be used to implicitly define the connectivity of a mesh. Instead of explicitly maintaining connectivity information, this approach simply keeps a collection of weights associated to each vertex. It consists of an algorithm to compute a WDT from any given triangulation, which relies on a breadth-first traversal to assign weights to vertices, and a subdivision strategy to ensure that the reconstructed triangulation conforms with the original one. This technique has many applications and, in particular, it allows for a very simple method of merging triangulations, which is illustrated with both 2D and 3d examples.

Diese Arbeit befasst sich mit der unimodularen Überdeckung und Triangulierung von Gitterpolytopen. Zentral ist in diesem Zusammenhang die Angabe einer möglichst guten oberen Schranke c0, so dass die Vielfachen cP eines Polytopes P für alle c>c0 eine unimodulare Überdeckung besitzen. Bruns und Gubeladze haben erstmals die Existenz einer solchen Schranke nachgewiesen und konnten sogar explizit eine solche in Abhängigkeit von der Dimension des Polytopes angeben. Allerdings war diese Schranke super-exponentiell. In dieser Arbeit wird nun u.a. eine polynomielle obere Schranke hergeleitet.

In this thesis, all the possible semi-prewavelets over uniform refinements of regular triangulations have been studied. A corresponding theorem is given to ensure the linear independence of a set of different pre-wavelets obtained by summing pairs of these semi-prewavelets. This provides efficient multiresolutions of the spaces of functions over various regular triangulation domains since the bases of the orthogonal complements of the coarse spaces can be constructed very easily.

No description available.

On considère, en deux dimensions, une version euclidienne discrète de l’action d’Einstein-Hilbert, qui décrit la gravité en l’absence de matière. À l’intégration sur les géométries se substitue une sommation sur des surfaces triangulées aléatoires. Dans la limite physique de faible gravité, seules les triangulations planaires survivent. Leur limite en distribution, la carte brownienne, est une surface fractale continue dont l’importance dans le contexte de la gravité quantique en deux dimensions a été récemment précisée. Cet espace est interprété comme un espace-temps quantique, obtenu comme limite à grande échelle d’un ensemble statistique de surfaces discrètes aléatoires. En deux dimensions, on peut donc étudier les propriétés fractales de la gravité quantique via une approche discrète. Il est bien connu que les généralisations directes en dimensions supérieures échouent à produire des espace-temps quantiques aux propriétés adéquates : en dimension D>2, la limite en distribution des triangulations qui survivent dans la limite de faible gravité est l’arbre continu aléatoire, ou polymères branchés en physique. Si en deux dimensions on parvient aux mêmes conclusions en considérant non pas des triangulations, mais des surfaces discrètes aléatoires obtenues par recollements de 2p-gones, nous savons depuis peu que ce n’est pas toujours le cas en dimension D>2. L’apparition de nouvelles limites continues dans le cadre de théories de gravité impliquant des espaces discrets aléatoires reste une question ouverte. Nous étudions des espaces obtenus par recollements de blocs élémentaires, comme des polytopes à facettes triangulaires. Dans la limite de faible gravité, seuls les espaces qui maximisent la courbure moyenne survivent. Les identifier est cependant une tâche ardue dans le cas général, pour lequel les résultats sont obtenus numériquement. Afin d’obtenir des résultats analytiques, une coloration des (D-1)-cellules, les facettes, a été introduite. En toute dimension paire, on peut trouver des familles d’espaces discrets colorés de courbure moyenne maximale dans la classe d’universalité des arbres – convergeant vers l’arbre continu aléatoire, des cartes planaires – convergeant vers la carte brownienne, ou encore dans la classe de prolifération des bébé-univers. Cependant, ces résultats sont obtenus en raison de la simplicité de blocs élémentaires dont la structure uni ou bidimensionnelle ne rend pas compte de la riche diversité des blocs colorés en dimensions supérieures. Le premier objectif de cette thèse est donc d’établir des outils combinatoires qui permettraient une étude systématique des blocs élémentaires colorés et des espaces discrets qu’ils génèrent. Le principal résultat de ce travail est l’établissement d’une bijection entre ces espaces et des familles de cartes combinatoires, qui préserve l’information sur la courbure locale. Elle permet l’utilisation de résultats sur les surfaces discrètes et ouvre la voie à une étude systématique des espaces discrets en dimensions supérieures à deux. Cette bijection est appliquée à la caractérisation d’un certain nombre de blocs de petites tailles ainsi qu’à une nouvelle famille infinie. Le lien avec les modèles de tenseurs aléatoires est détaillé. Une attention particulière est donnée à la détermination du nombre maximal de (D-2)-cellules et de l’action appropriée du modèle de tenseurs correspondant. Nous montrons comment utiliser la bijection susmentionnée pour identifier les contributions à un tout ordre du développement en 1/N des fonctions à 2n points du modèle SYK coloré, et appliquons ceci à l’énumération des cartes unicellulaires généralisées – les espaces discrets obtenus par recollement d’un unique bloc élémentaire – selon leur courbure moyenne. Pour tout choix de blocs colorés, nous montrons comment réécrire la théorie d’Einstein-Hilbert discrète correspondante comme un modèle de matrices aléatoires avec traces partielles, dit représentation en champs intermédiaires. / In two dimensions, the Euclidean Einstein-Hilbert action, which describes gravity in the absence of matter, can be discretized over random triangulations. In the physical limit of small Newton's constant, only planar triangulations survive. The limit in distribution of planar triangulations - the Brownian map - is a continuum fractal space which importance in the context of two-dimensional quantum gravity has been made more precise over the last years. It is interpreted as a quantum continuum space-time, obtained in the thermodynamical limit from a statistical ensemble of random discrete surfaces. The fractal properties of two-dimensional quantum gravity can therefore be studied from a discrete approach. It is well known that direct higher dimensional generalizations fail to produce appropriate quantum space-times in the continuum limit: the limit in distribution of dimension D>2 triangulations which survive in the limit of small Newton's constant is the continuous random tree, also called branched polymers in physics. However, while in two dimensions, discretizing the Einstein-Hilbert action over random 2p-angulations - discrete surfaces obtained by gluing 2p-gons together - leads to the same conclusions as for triangulations, this is not always the case in higher dimensions, as was discovered recently. Whether new continuum limit arise by considering discrete Einstein-Hilbert theories of more general random discrete spaces in dimension D remains an open question.We study discrete spaces obtained by gluing together elementary building blocks, such as polytopes with triangular facets. Such spaces generalize 2p-angulations in higher dimensions. In the physical limit of small Newton's constant, only discrete spaces which maximize the mean curvature survive. However, identifying them is a task far too difficult in the general case, for which quantities are estimated throughout numerical computations. In order to obtain analytical results, a coloring of (D-1)-cells has been introduced. In any even dimension, we can find families of colored discrete spaces of maximal mean curvature in the universality classes of trees - converging towards the continuous random tree, of planar maps - converging towards the Brownian map, or of proliferating baby universes. However, it is the simple structure of the corresponding building blocks which makes it possible to obtain these results: it is similar to that of one or two dimensional objects and does not render the rich diversity of colored building blocks in dimensions three and higher.This work therefore aims at providing combinatorial tools which would enable a systematic study of the building blocks and of the colored discrete spaces they generate. The main result of this thesis is the derivation of a bijection between colored discrete spaces and colored combinatorial maps, which preserves the information on the local curvature. It makes it possible to use results from combinatorial maps and paves the way to a systematical study of higher dimensional colored discrete spaces. As an application, a number of blocks of small sizes are analyzed, as well as a new infinite family of building blocks. The relation to random tensor models is detailed. Emphasis is given to finding the lowest bound on the number of (D-2)-cells, which is equivalent to determining the correct scaling for the corresponding tensor model. We explain how the bijection can be used to identify the graphs contributing at any given order of the 1/N expansion of the 2n-point functions of the colored SYK model, and apply this to the enumeration of generalized unicellular maps - discrete spaces obtained from a single building block - according to their mean curvature. For any choice of colored building blocks, we show how to rewrite the corresponding discrete Einstein-Hilbert theory as a random matrix model with partial traces, the so-called intermediate field representation.

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

Ces travaux s'inscrivent dans la thématique de l'inférence géométrique dont le but est de répondre au problème suivant : étant donné un objet géométrique dont on ne connaît qu'une approximation, peut-on estimer de manière robuste ses propriétés? On se place dans cette thèse dans le cas où l'approximation est un nuage de points ou un ensemble digital dans un espace euclidien de dimension finie. On montre tout d'abord un résultat de stabilité d'un estimateur de normale basé sur l'analyse en composante principale, ainsi qu'un résultat de convergence multigrille d'un estimateur du Voronoi Covariance Measure qui utilise des matrices de covariance de cellules de Voronoi. Ces deux résultats, comme la plupart des résultats en inférence géométrique, utilisent la stabilité de la fonction distance à un compact. Cependant, la présence d'un seul point aberrant suffit pour que les hypothèses des résultats de stabilité ne soient pas satisfaites. La distance à une mesure est une fonction distance généralisée introduite récemment qui est robuste aux points aberrants. Dans ce travail, on généralise le Voronoi Covariance Measure à des fonctions distances généralisées et on montre que cet estimateur appliqué à la distance à une mesure est robuste aux points aberrants. On en déduit en particulier un estimateur de normale très robuste. On présente également des résultats expérimentaux qui montrent une forte robustesse des estimations de normales, courbures, directions de courbure et arêtes vives. Ces résultats sont comparés favorablement à l'état de l'art. / The purpose of geometric inference is to answer the following problem : Given a geometric object that is only known through an approximation, can we get a robust estimation of its properties? We consider in this thesis the case where the approximation is a point cloud or a digital set in a finite dimensional Euclidean space. We first show a stability result for a normal estimator based on the principal component analysis, as well as a result of multigrid convergence of an estimator of the Voronoi covariance measure, which uses covariance matrices of Voronoi cells. As most of geometric inference results, these two last results use the robustness of the distance function to a compact set. However, the presence of a single outlier is sufficient to make the assumptions of these results not satisfied. The distance to a measure is a generalized distance function introduced recently, that is robust to outliers. In this work, we generalize the Voronoi Covariance Measure to generalized distance functions and we show that this estimator applied to the distance to a measure is robust to outliers. We deduce a very robust normal estimator. We present experiments showing the robustness of our approach for normals, curvatures, curvature directions and sharp features estimation. These results are favorably compared to the state of the art.

In this thesis, we undertake a combinatorial study of certain aspects of triangulations of cartesian products of simplices, particularly in relation to their relevance in toric algebra and to their underlying product structure. The first chapter reports joint work with Samu Potka. The object of study is a class of homogeneous toric ideals called cut ideals of graphs, that were introduced by Sturmfels and Sullivant 2006. Apart from their inherent appeal to combinatorial commutative algebra, these ideals also generalize graph statistical models for binary data and are related to some statistical models for phylogenetic trees. Specifically, we consider minimal free resolutions for the cut ideals of trees. We propose a method to combinatorially estimate the Betti numbers of the ideals in this class. Using this method, we derive upper bounds for some of the Betti numbers, given by formulas exponential in the number of vertices of the tree. Our method is based on a common technique in commutative algebra whereby arbitrary homogeneous ideals are deformed to initial monomial ideals, which are easier to analyze while conserving some of the information of the original ideals. The cut ideal of a tree on n vertices turns out to be isomorphic to the Segre product of the cut ideals of its n-1 edges (in particular, its algebraic properties do not depend on its shape). We exploit this product structure to deform the cut ideal of a tree to an initial monomial ideal with a simple combinatorial description: it coincides with the edge ideal of the incomparability graph of the power set of the edges of the tree. The vertices of the incomparability graph are subsets of the edges of the tree, and two subsets form an edge whenever they are incomparable. In order to obtain algebraic information about these edge ideals, we apply an idea introduced by Dochtermann and Engström in 2009 that consists in regarding the edge ideal of a graph as the (monomial) Stanley-Reisner ideal of the independence complex of the graph. Using Hochster\''s formula for computting Betti numbers of Stanley-Reisner ideals by means of simplicial homology, the computation of the Betti numbers of these monomial ideals is turned to the enumeration of induced subgraphs of the incomparability graph. That the resulting values give upper bounds for the Betti numbers of the cut ideals of trees is an important well-known result in commutative algebra. In the second chapter, we focus on some combinatorial features of triangulations of the point configuration obtained as the cartesian product of two standard simplices. These were explored in collaboration with César Ceballos and Arnau Padrol, and had a two-fold motivation. On the one hand, we intended to understand the influence of the product structure on the set of triangulations of the cartesian product of two point configurations; on the other hand, the set of all triangulations of the product of two simplices is an intricate and interesting object that has attracted attention both in discrete geometry and in other fields of mathematics such as commutative algebra, algebraic geometry, enumerative geometry or tropical geometry. Our approach to both objectives is to examine the circumstances under which a triangulation of the polyhedral complex given by the the product of an (n-1)-simplex times the (k-1)-skeleton of a (d-1)-simplex extends to a triangulation of an (n-1)-simplex times a (d-1)-simplex. We refer to the former as a partial triangulation of the product of two simplices. Our main result says that if d >= k > n, a partial triangulation always extends to a uniquely determined triangulation of the product of two simplices. A somewhat unexpected interpretation of this result is as a finiteness statement: it asserts that if d is sufficiently larger than n, then all partial triangulations are uniquely determined by the (compatible) triangulations of its faces of the form “(n-1)-simplex times n-simplex”. Consequently, one can say that in this situation ‘\''triangulations of an (n-1)-simplex times a (d-1)-simplex are not much more complicated than triangulations of an (n-1)-simplex times an n-simplex\''\''. The uniqueness assertion of our main result holds already when d>=k>=n. However, the same is not true for the existence assertion; namely, there are non extendable triangulations of an (n-1)-simplex times the boundary of an n-simplex that we explicitly construct. A key ingredient towards this construction is a triangulation of the product of two (n-1)-simplices that can be seen as its ``second simplest triangulation\''\'' (the simplest being its staircase triangulation). It seems to be knew, and we call it the Dyck path triangulation. This triangulation displays symmetry under the cyclic group of order n that acts by simultaneously cycling the indices of the points in both factors of the product. Next, we exhibit a natural extension of the Dyck path triangulation to a triangulation of an (n-1)-simplex times an n-simplex that, in a sense, enjoys some sort of ‘\''rigidity\''\'' (it also seems new). Performing a ‘\''local modification\''\'' on the restriction of this extended triangulation to the polyhedral complex given by (n-1)-simplex times the boundary of an n-simplex yields the non-extendable partial triangulation. The thesis includes two appendices on basic commutative algebra and triangulations of point configuration, included to make it slightly self-contained.

This thesis is devoted to the problem of finding a suitable geometrical de- scription of the domain for the Finite Element Method (FEM). We present the most important methods used in generation and improvement of unstructured triangular meshes (grids) for two dimensional FEM. Possible measures of mesh quality are discussed with respect to their usage in linear Lagrange FEM. The relationship between mesh geometry (especially angles of particular triangles), discretization error and stiffness matrix condition number is examined. Two methods of mesh improvement, based on Centroidal Voronoi Tessellations (CVT) and Optimal Delaunay Triangulations (ODT), are discussed in detail and some results on convergence of CVT based methods are reviewed. Some aspects of these methods, e.g. the relation between density of boundary points and interior mesh vertices and the treatment of the boundary triangles is reconsidered in a new way. We have implemented these two methods and we discuss possible im- provements and new algorithms. A geometrically very interesting idea of recent alternative to FEM, Isogeometric Analysis (IGA), is outlined and demonstrated on a simple example. Several numerical tests are made in order to the compare the accuracy of solutions of isotropic PDEs obtained by FEM on bad mesh, mesh improved...