Diagrammes de Voronoi généraux et applications

Voronoi diagrams are fundamental data structures that have been extensively studied in Computational Geometry. A Voronoi diagram can be defined as the minimization diagram of a finite set of continuous functions. Usually, each of those functions is interpreted as the distance function to an object. The associated Voronoi diagram subdivides the embedding space into regions, each region consisting of the points that are closer to a given object than to the others. We may define many variants of Voronoi diagrams depending on the class of objects, the distance functions and the embedding space.Affine diagrams, i.e. diagrams whose cells are convex polytopes, are well understood. Their properties can be deduced from the properties of polytopes and they can be constructed efficiently.The first part of this thesis is dedicated to the presentation and classification of Voronoi diagrams. We discuss the most studied varieties of Voronoi diagrams, before putting these diagrams in the context of abstract Voronoi diagrams, a notion inherited from Klein. This allows us to present in a general setting the question of recognizing classical Voronoi diagrams by looking at their bisectors, a point of view initiated by Aurenhammer.In the second part, we focus on the study of anisotropic Voronoi diagrams, and the ways of computing their dual mesh, if it is well defined. If the dual mesh is not well defined, we study some ways of refining the diagram in order to obtain a well-defined dual. We first use the definitions of Labelle and Shewchuk and the linearization procedure, as presented in the previous part. This allows us to define an algorithm which is the natural consequence of Part~I.The third part is then devoted to a different approach to anisotropic meshing. By changing the definition of an anisotropic mesh into the one of a locally uniform anisotropic mesh, we allow the design of simple anisotropic mesh generation algorithms in 2D and 3D.Finally, the fourth part of this thesis is devoted to the application of a different kind of Voronoi diagrams, namely power diagrams, to the question of greedy routing in ad hoc networks. There again, the local properties of triangulations play a crucial role. We prove how some local properties of regular triangulations, which are a generalization of Delaunay triangulations, imply global properties in terms of routing.Les diagrammes de Voronoi sont des structures de données fondamentales qui ont été étudiées en détail dans le domaine de la géométrie algorithmique. Un diagramme de Voronoi peut être défini comme le diagramme de minimisation d'un ensemble fini de fonctions continues. On interprète en général chacune de ces fonctions comme la fonction distance à un objet. Le diagramme de Voronoi correspondant partitionne l'espace de définition en régions, chacune d'entre elle réunissant les points qui sont plus proches d'un object que de tous les autres. On peut définir de nombreuses variantes des diagrammes de Voronoi, selon les classes d'objets, de fonctions distance et d'espace de définition considérés. Les diagrammes affines, c'est-à-dire les diagrammes dont les cellules sont des polytopes convexes, sont bien connus. Leurs propriétés peuvent être déduites de celles des polytopes, et on peut les construire efficacement. La première partie de cette thèse s'attache à présenter et classifier les diagrammes de Voronoi. Nous cataloguons les variétés de diagrammes de Voronoi les plus étudiées, avant de les replacer dans le contexte des diagrammes de Voronoi abstraits, une notion initialement proposée par Klein. Cela nous permet de présenter dans un cadre général la question de la caractérisation des diagrammes de Voronoi classiques en fonction de la forme de leurs bissecteurs, un point de vue développé d'abord par Aurenhammer.Dans une deuxième partie, nous nous concentrons sur l'étude des diagrammes de Voronoi anisotropes, et sur les façons de calculer leur maillage dual, dans les cas où il est bien défini. Si celui-ci ne l'est pas, nous étudions des méthodes de raffinement du diagramme en vue d'obtenir un dual bien défini. Nous utilisons d'abord les définitions de Labelle et Shewchuk et la procédure de linéarisation présentée dans la partie précédente. Cela nous permet ensuite de définir un algorithme qui apparaît comme une conséquence naturelle de la première partie.La troisième partie est consacrée à une approche différente de la génération de maillages anisotropes. En remplaçant la définition de maillage anisotrope par celle de maillage anisotrope localement uniforme, nous parvenons à construire simplement un algorithme prouvé de génération de maillage anisotrope en dimension 2 et 3.Enfin, la quatrième partie de cette thèse considère l'application d'un autre type de diagramme de Voronoi, les diagrammes de puissance, à la question du routage glouton dans les réseaux ad hoc. Ici encore, les propriétés locales des triangulations jouent un rôle crucial. Nous montrons comment l'obtention de certaines propriétés locales des triangulations régulières, qui sont une généralisation des triangulations de Delaunay, permet de garantir des propriétés globales en termes de routage