Abstract FR:

La construction du diagramme de Voronoi est un problème fondamental de l'algorithmique géométrique et a des applications en cristallographie, en physique, en chimie, en climatologie, en géographie et en informatique. Etant donné un ensemble fini S de n points dans le plan ou dans l'espace tridimensionnel E on associe à chaque point s de S l'ensemble V(s) des points de E plus proches de s que de tous les autres sites de S. Les ensembles V(s) définissent un diagramme appelé le diagramme de Voronoi de S. Le dual géométrique de ce diagramme est appelé le diagramme de Delaunay et est noté Del(S). Un algorithme, variante des algorithmes de Lee et Schachter, Guibas et Stolfi, de construction de ces diagrammes en O(nlogn) dans le plan utilisant les cartes est présenté. La notion de pavage qui généralise à l'espace celle de la carte est utilisée pour l'algorithme de construction des diagrammes dans l'espace. Cet algorithme est en O(n2) ce qui est optimal. Il résoud tous les cas particuliers et détermine le diagramme de Delaunay et non une tétraédrisation qui le raffine. Nos algorithmes sont, en plus, robustes. Ils utilisent des approximations géométriques de nature angulaire et permettent d'avoir pour toute similitude T, T(Del(S)) = Del(T(S))