Diagrammes de Voronoï

TRÈS BIENTÔT SUR VOTRE ÉCRAN UNE VERSION PLUS COMPLETE

Définition : Soit S un ensemble de n sites de l'espace euclidien en dimension d. Pour chaque site p de S, la cellule de Voronoï V(p) de p est l'ensemble des points de l'espace qui sont plus proches de p que de tous les autres sites de S. Le diagramme de Voronoï de V(S) est la décomposition de l'espace formée par les cellules de Voronoï des sites.
Définition : La triangulation de Delaunay de S est le dual géométrique du diagramme de Voronoï de S : deux points de S sont reliés par une arête dans la triangulation de Delaunay si et seulement si leurs cellules sont adjacentes dans le diagramme de Voronoï de S.

Les diagrammes de Voronoï sont des structures très utiles, rencontrées fréquemment car elles permettent de représenter des relations de distance entre objets et des phénomènes de croissance : il n'est pas étonnant de les voir utilisés pour modéliser des cristaux ou les grandes structures de l'univers, et de les trouver souvent dans la nature, par exemple sur la carapace d'une tortue ou sur le cou d'une girafe réticulée. Les diagrammes de Voronoï sont aussi des structures de données permettant de résoudre de nombreux problèmes~: recherche de plus proches voisins et planification de mouvements notamment. L'étude des diagrammes de Voronoï, de leurs propriétés mathématiques, de leur calcul et de leurs nombreuses variantes a été et reste un sujet d'importance majeure de la géométrie algorithmique. Les contributions du projet Prisme portent sur les aspects combinatoires et algorithmiques, l'extension à différentes métriques non euclidiennes et l'application aux problèmes de reconstruction de formes.

Last modified: Fri Jan 7 08:50:35 MET 2000 Olivier Devillers Thèmes Accueil PRISME same page in english