Title: Generalized Voronoi Diagrams and Applications
Abstract: 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.