Abstract FR:

Etant donné un ensemble S de sites dans l'espace euclidien E de dimension D, le diagramme de Voronoi de S est la partition de E dont chaque région est l'ensemble des points de E qui sont plus proches d'un site de S que de tous les autres. Le diagramme de Voronoi admet un dual orthogonal appelé le diagramme de Delaunay. Dans la première partie de cette thèse, nous étudions les propriétés angulaires des diagrammes de Delaunay. Nous généralisons la propriété d'équiangularité aux diagrammes de Delaunay du plan et une propriété d'équiangularité locale aux diagrammes de Delaunay en dimension quelconque. Nous établissons aussi une propriété duale de l'équiangularité, la coéquiangularité, qui caractérise les diagrammes de Delaunay en toute dimension en utilisant des angles de droites ou des angles solides. Dans la deuxième partie, nous étudions une généralisation du diagramme de Voronoi, le diagramme de Voronoi d'ordre k. Nous définissons un diagramme de puissance équivalent à un diagramme de Voronoi d'ordre k donné ainsi qu'un diagramme de puissance d'ordre 1 équivalent à un diagramme de puissance d'ordre k. Nous définissons aussi un dual orthogonal du diagramme de Voronoi d'ordre k, le diagramme de Delaunay d'ordre k, et prouvons que ce diagramme forme une partition de l'espace. Dans la dernière partie, nous proposons deux algorithmes qui construisent les diagrammes de Delaunay d'ordre k dans le plan et dans l'espace de dimension 3 et nous simplifions le calcul de la taille du diagramme de Delaunay d'ordre k dans le plan