Cette thèse présente une construction générale d'ondelettes de seconde génération dont l'originalité est de distinguer deux points vues complémentaires : le point de vue de subdivision, qui souligne le lien bien connu entre les schémas de subdivision et l'analyse multirésolution, et d'autre part le point de vue non emboîté, dans lequel les espaces d'approximation, qui remplacent les espaces d'échelle traditionnels, ne sont plus nécessairement imbriqués. Dans la première partie de la thèse, le cadre multirésolution est présenté puis divers aspects théoriques, essentiellement relatifs au point de vue non emboîté, sont étudiés. En particulier, plusieurs techniques de constructions des opérateurs d'analyse ou de synthèse sont présentées. La deuxième partie de la thèse est consacrée aux applications. Le point de vue non emboîté est utilisé pour développer un cadre multirésolution pour fonctions constantes ou linéaires par morceaux définies sur des triangulations irrégulières d'un domaine planaire ou sphérique, permettant notamment la visualisation progressive de grands volumes de données. Les algorithmes de décomposition et de reconstruction des données sont discutés en détails notamment du point de vue de leur implémentation effective, plus délicate que dans le cas des ondelettes classiques. Des applications traditionnelles telles que la compression ou l'édition à différents niveaux de détails sont également généralisées à ces fonctions. D'autre part, est également discutée l'utilisation du cadre non emboîté pour l'approximation et la reconstruction de fonctions définies sur des maillages surfaciques construits via des modèles multirésolution basés sur les techniques de décimation de maillages. Enfin, on montre à diverses reprises que le point de vue non emboîté permet un abord unifié des algorithmes basés sur les ondelettes et des techniques décimatoires, traditionnellement opposées.

<p>This thesis consists of three papers, all of them on the topic of function spaces on fractals.</p><p>The papers summarised in this thesis are:</p><p>Paper I Mats Bodin, Wavelets and function spaces on Mauldin-Williams fractals, Research Report in Mathematics No. 7, Umeå University, 2005.</p><p>Paper II Mats Bodin, Harmonic functions and Lipschitz spaces on the Sierpinski gasket, Research Report in Mathematics No. 8, Umeå University, 2005.</p><p>Paper III Mats Bodin, A discrete characterisation of Lipschitz spaces on fractals, Manuscript.</p><p>The first paper deals with piecewise continuous wavelets of higher order in Besov spaces defined on fractals. A. Jonsson has constructed wavelets of higher order on fractals, and characterises Besov spaces on totally disconnected self-similar sets, by means of the magnitude of the coefficients in the wavelet expansion of the function. For a class of fractals, W. Jin shows that such wavelets can be constructed by recursively calculating moments. We extend their results to a class of graph directed self-similar fractals, introduced by R. D. Mauldin and S. C. Williams.</p><p>In the second paper we compare differently defined function spaces on the Sierpinski gasket. R. S. Strichartz proposes a discrete definition of Besov spaces of continuous functions on self-similar fractals having a regular harmonic structure. We identify some of them with Lipschitz spaces introduced by A. Jonsson, when the underlying domain is the Sierpinski gasket. We also characterise some of these spaces by means of the magnitude of the coefficients of the expansion of a function in a continuous piecewise harmonic base.</p><p>The last paper gives a discrete characterisation of certain Lipschitz spaces on a class of fractal sets. A. Kamont has discretely characterised Besov spaces on intervals. We give a discrete characterisation of Lipschitz spaces on fractals admitting a type of regular sequence of triangulations, and for a class of post critically finite self-similar sets. This shows that, on some fractals, certain discretely defined Besov spaces, introduced by R. Strichartz, coincide with Lipschitz spaces introduced by A. Jonsson and H. Wallin for low order of smoothness.</p>

This thesis consists of three papers, all of them on the topic of function spaces on fractals. The papers summarised in this thesis are: Paper I Mats Bodin, Wavelets and function spaces on Mauldin-Williams fractals, Research Report in Mathematics No. 7, Umeå University, 2005. Paper II Mats Bodin, Harmonic functions and Lipschitz spaces on the Sierpinski gasket, Research Report in Mathematics No. 8, Umeå University, 2005. Paper III Mats Bodin, A discrete characterisation of Lipschitz spaces on fractals, Manuscript. The first paper deals with piecewise continuous wavelets of higher order in Besov spaces defined on fractals. A. Jonsson has constructed wavelets of higher order on fractals, and characterises Besov spaces on totally disconnected self-similar sets, by means of the magnitude of the coefficients in the wavelet expansion of the function. For a class of fractals, W. Jin shows that such wavelets can be constructed by recursively calculating moments. We extend their results to a class of graph directed self-similar fractals, introduced by R. D. Mauldin and S. C. Williams. In the second paper we compare differently defined function spaces on the Sierpinski gasket. R. S. Strichartz proposes a discrete definition of Besov spaces of continuous functions on self-similar fractals having a regular harmonic structure. We identify some of them with Lipschitz spaces introduced by A. Jonsson, when the underlying domain is the Sierpinski gasket. We also characterise some of these spaces by means of the magnitude of the coefficients of the expansion of a function in a continuous piecewise harmonic base. The last paper gives a discrete characterisation of certain Lipschitz spaces on a class of fractal sets. A. Kamont has discretely characterised Besov spaces on intervals. We give a discrete characterisation of Lipschitz spaces on fractals admitting a type of regular sequence of triangulations, and for a class of post critically finite self-similar sets. This shows that, on some fractals, certain discretely defined Besov spaces, introduced by R. Strichartz, coincide with Lipschitz spaces introduced by A. Jonsson and H. Wallin for low order of smoothness.

Soit S un ensemble de points pris sur une surface F d'équation z = f(x,y) ; on projette S dans le plan (xOy), et on désire construire une triangulation de l'enveloppe convexe de la projection de S qui déterminera une approximation linéaire par morceaux de F, dont la qualité sera liée à une mesure de l'erreur d'approximation de la surface. Il a été récemment prouvé que la triangulation de Delaunay était optimale pour des critères de normes Lp, lorsqu'il s'agissait d'approcher linéairement toute fonction quadratique convexe, dans un espace de dimension quelconque. En revanche, très peu de recherches ont été menées lorsque la surface n'est pas convexe. Ce mémoire propose donc d'étudier l'approximation par une tri- angulation, pour des critères de normes L1 et L2, d'une surface non convexe d'équation la plus simple possible : le paraboloïde hyperbolique défini par z = x2 − y2. Une construction est ainsi donnée pour déterminer, de manière naturelle, les courbes de séparation d'un triangle ∆, c'est-à-dire les limites du plan pour lesquelles ∆ doit être conservé dans une triangulation localement op- timale du paraboloïde hyperbolique. Des algorithmes de triangulation qui font appel à diverses heuristiques fondées sur les courbes de séparation ont été abon- damment testés ; une amélioration significative par rapport à la triangulation de Delaunay a été mise en évidence. Une comparaison avec des triangulations glob- alement optimales, dont l'obtention n'est possible qu'au moyen de programmes de complexité exponentielle, prouve que ces algorithmes rendent finalement de "bonnes" triangulations. Les recherches montrent qu'un tel procédé peut facile- ment être généralisé à toutes les surfaces définies par des fonctions quadratiques, de la forme z = αx2 + βy2 + γxy + δ1x + δ2y + δ3.

Cette thèse propose de nouvelles méthodes pour accélérer certaines des plus importantes opérations dans une triangulation de Delaunay, conciliant efficacité et bonne complexité théorique. Nous proposons deux approches pour calculer la triangulation de Delaunay de points sur (ou proches) d'une sphère. La première approche calcule la triangulation de Delaunay de points exactement sur la sphère par construction. La deuxième approche calcule directement l'enveloppe convexe de l'ensemble d'entrée, et donne quelques garanties sur la sortie. Les deux approches sont basées sur la triangulation régulière sur la sphère. La deuxième approche améliore les solutions de l'état de l'art. L'operation de mise à jour d'une triangulation de Delaunay, quand les sommets bougent, est critique dans plusieurs domaines d'applications. Quand tous les sommets bougent, reconstruire toute la triangulation est étonnamment une bonne solution en pratique. Toutefois, lorsque les points se déplacent tres peu, ou si seulement une fraction des sommets bougent, la reconstruction n'est plus la meilleure option. Nous proposons un système de filtrage basé sur le concept de tolérance d'un sommet. Nous avons mené plusieurs expériences pour évaluer le comportement de l'algorithme sur des ensembles de données variés. Les expériences ont montré que l'algorithme est particulièrement pertinent pour les régimes convergents tels que les itérations de Lloyd. En dimension deux, l'algorithme présenté est un ordre de grandeur plus rapide que la reconstruction pour les itérations de Lloyd. En dimension trois, l'algorithme présenté a des performances équivalentes à la reconstruction quand tous les sommets bougent, cependant il est entièrement dynamique et améliore les solutions dynamiques précédentes. Ce résultat permet d'aller plus loin dans le nombre d'itérations de façon à produire des maillages de qualité supérieure. La localisation de points dans une subdivision de l'espace est un classique de la géométrie algorithmique; nous réexaminons ce problème dans le cas des triangulations de Rd pour exploiter une éventuelle cohérence entre les requêtes. Nous analysons, implementons, et évaluons une strategie de localisation de point adaptable aux distributions des requêtes, basée sur Jump & Walk, appellée Keep, Jump, &Walk. Pour des paquets de requêtes, l'idée principale est d'utiliser les requêtes précédentes pour améliorer le traitement de la requête courante. Maintenant à propos de la complexité d'une requête dans une triangulation de Delaunay, nous montrons que la hiérarchie de Delaunay peut être utilisée pour localiser un point q à partir d'une requête précédente p avec une complexité randomisée O(log ](pq)) pourvu que la triangulation vérifie certaines hypothèses (](s) désigne le nombre de simplex traversés par le segment s). Finalement, nous combinons la bonne adaptabilité à la distribution des requêtes du Keep, Jump, & Walk, et la bonne complexité de la hiérarchie de Delaunay, en une nouvelle stratégie de localisation de points appellée Keep, Jump, & Climb. Selon nos connaissances, Keep, Jump, & Climb est le premier algorithme adaptable aux distributions des requêtes qui marche en pratique et en théorie pour les triangulations de Delaunay--dans nos expérimentations, Keep, Jump, & Climb est plus rapide que la hiérarchie de Delaunay indépendamment de la cohérence spatiale des requêtes, et significativement plus rapide quand la cohérence spatiale est forte.

Si la communauté internationale de géométrie algorithmique a souvent<br />la tentation de s'engouffrer dans des recherches essentiellement<br />théoriques, et en particulier combinatoires, la grande originalité des<br />travaux à l'INRIA résidait déjà à l'époque de mes débuts dans le<br />souci de leur validation expérimentale et de leur applicabilité. <br /><br />Le domaine a suivi globalement une évolution dans cette direction,<br />en particulier grâce à l'``Impact Task Force Report''. Notre intérêt pour le transfert technologique et<br />industriel, ainsi que pour l'établissement d'une plateforme pour la<br />recherche, a pris pendant ce temps une tournure encore plus concrète<br />avec notre implication très forte dans le projet CGAL<br />dont notre équipe est l'un des moteurs.<br /><br />Ce document prend le parti de présenter les travaux sous l'angle de<br />cette préoccupation pratique.<br />Il comporte deux chapitres principaux : le premier rassemble<br />des travaux sur les triangulations, le second présente des travaux sur<br />les objets courbes. Ces deux chapitres se concluent par un ensemble de<br />directions ouvertes. Le troisième chapitre survole rapidement d'autres<br />résultats.

Nous étudions certaines décompositions de M en polyèdres idéaux, où M est une variété hyperbolique à pointe(s), de dimension 3. Par un théorème d'Epstein et Penner, il existe une telle décomposition, dite ``de Delaunay'', canonique en un sens géométrique. <br /><br />Au chapitre 1 nous trouvons la décomposition de Delaunay quand M fibre sur le cercle avec pour fibre un tore percé. La méthode consiste à ``deviner'' la <br />combinatoire de la décomposition, puis à trouver des angles dièdres positifs pour ses polyèdres combinatoires : un théorème de Rivin dit que tout point critique de la fonctionelle volume dans l'espace de déformation des angles dièdres fournit la métrique hyperbolique. Les inégalités établies pour montrer l'existence d'un tel point critique permettent alors de vérifier que la décomposition est bien de Delaunay. <br /><br />Au chapitre 2 nous étendons la méthode à certains complémentaires d'entrelacs (entrelacs à 2 ponts notamment). Au chapitre 3 nous l'étendons aux coeurs convexes de groupes quasi-fuchsiens du tore percé (la décomposition est alors infinie, et certaines <br />pièces ne sont pas des polyèdres). Nous obtenons ainsi une nouvelle preuve du théorème des laminations de plissage pour le tore percé. Au chapitre 4, nous étendons partiellement la méthode aux complémentaires d'entrelacs arborescents : sans <br />trouver de point critique, nous caractérisons les entrelacs arborescents hyperboliques. <br /><br />Au chapitre 5, qui éclaire un passage du chapitre 3, nous montrons que certains polynômes de Laurent, qui généralisent les nombres de Markoff, n'ont que des coefficients positifs.

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.

Triangle mesh models of images are studied. Through exploration, a computational framework for mesh generation based on data-dependent triangulations (DDTs) and two specific mesh-generation methods derived from this framework are proposed. In earlier work, Yang et al. proposed a highly-effective technique for generating triangle-mesh models of images, known as the error diffusion (ED) method. Unfortunately, the ED method, which chooses triangulation connectivity via a Delaunay triangulation, typically yields triangulations in which many (triangulation) edges crosscut image edges (i.e., discontinuities in the image), leading to increased approximation error. In this thesis, we propose a computational framework for mesh generation that modifies the ED method to use DDTs in conjunction with the Lawson local optimization procedure (LOP) and has several free parameters. Based on experimentation, we recommend two particular choices for these parameters, yielding two specific mesh-generation methods, known as MED1 and MED2, which make different trade offs between approximation quality and computational cost. Through the use of DDTs and the LOP, triangulation connectivity can be chosen optimally so as to minimize approximation error. As part of our work, two novel optimality criteria for the LOP are proposed, both of which are shown to outperform other well known criteria from the literature. Through experimental results, our MED1 and MED2 methods are shown to yield image approximations of substantially higher quality than those obtained with the ED method, at a relatively modest computational cost. For example, in terms of peak-signal-to-noise ratio, our MED1 and MED2 methods outperform the ED method, on average, by 3.26 and 3.81 dB, respectively. / Graduate

Diese Arbeit befaßt sich mit der Koppelung von Vertex-Modellen an die planaren $\phi^4$-Zufallsgraphen des Zugangs zur Quantengravitation über dynamische Polygonifizierungen. Das betrachtete System hat eine doppelte Bedeutung, einerseits als die Koppelung einer konformen Feldtheorie mit zentraler Ladung $C=1$ an zweidimensionale Euklidische Quantengravitation, andererseits als Anwendung von geometrischer, "annealed" Unordnung auf ein prototypisches Modell der statistischen Mechanik. Da das Modell mit Hilfe einer großangelegten Reihe von Monte Carlo Simulationen untersucht wird, müssen entsprechende Techniken für die Simulation von dynamischen Quadrangulierungen bzw. die dualen $\phi^4$-Graphen entwickelt werden. Hierzu werden verschiedene Algorithmen und die dazugehörigen Züge vorgeschlagen und hinsichtlich ihrer Ergodizität und Effizienz untersucht. Zum Vergleich mit exakten Ergebnissen werden die Verteilung der Koordinationszahlen bzw. bestimmte Analoga davon konstruiert. Für Simulationen des $F$-Modells auf $\phi^4$-Zufallsgraphen wird ein Ordnungsparameter für den antiferroelektrischen Phasenübergang mit Hilfe einer Plakettenspindarstellung formuliert. Ausführliche "finite-size scaling"-Analysen des Kosterlitz-Thouless-Phasenübergangs des $F$-Modells auf dem Quadratgitter und auf Zufallsgraphen werden vorgestellt und die Positionen der jeweiligen kritischen Punkte sowie die dazugehörigen kritischen Exponenten werden bestimmt. Die Rückreaktion des Vertex-Modells auf die Zufallsgraphen wird in Form der Koordinationszahlverteilung, der Verteilung der "Baby-Universen" und dem daraus resultierenden String-Suszeptibilitäts-Exponenten sowie durch die geometrische Zweipunktfunktion analysiert, die eine Schätzung der intrinsischen Hausdorff-Dimension des gekoppelten Systems liefert. / In this thesis, the coupling of ice-type vertex models to the planar $\phi^4$ random graphs of the dynamical polygonifications approach to quantum gravity is considered. The investigated system has a double significance as a conformal field theory with central charge $C=1$ coupled to two-dimensional Euclidean quantum gravity and as the application of a special type of annealed connectivity disorder to a prototypic model of statistical mechanics. Since the model is analyzed by means of large-scale Monte Carlo simulations, suitable simulation techniques for the case of dynamical quadrangulations and the dual $\phi^4$ random graphs have to be developed. Different algorithms and the associated update moves are proposed and investigated with respect to their ergodicity and performance. For comparison to exact results, the co-ordination number distribution of the dynamical polygonifications model, or certain analogues of it, are constructed. For simulations of the 6-vertex $F$ model on $\phi^4$ random graphs, an order parameter for its anti-ferroelectric phase transitions is constructed in terms of a "plaquette spin" representation. Extensive finite-size scaling analyses of the Kosterlitz-Thouless point of the square-lattice and random graph $F$ models are presented and the locations of the critical points as well as the corresponding critical exponents are determined. The back-reaction of the coupled vertex model on the random graphs is investigated by an analysis of the co-ordination number distribution, the distribution of "baby universes" and the string susceptibility exponent as well as the geometric two-point function, yielding an estimate for the internal Hausdorff dimension of the coupled system.